189 lines
5.8 KiB
Python
189 lines
5.8 KiB
Python
class TuringMachine():
|
|
def __init__(self, turing_machine_def: str) -> None:
|
|
# if a placeholder is needed, create it with empty string
|
|
if not turing_machine_def:
|
|
return
|
|
|
|
# STATE VARIABLES
|
|
self.state_start: str = ''
|
|
self.state_accept: str = ''
|
|
self.state_reject: str = ''
|
|
self.state_current: str = ''
|
|
|
|
# BAND VARIABLES
|
|
self.band: list = []
|
|
self.band_num: int = 0
|
|
self.band_current: int = 0
|
|
|
|
# RULE VARIABLES
|
|
self.rules: list = []
|
|
self.rule_used: str = ''
|
|
|
|
# ERR Variables
|
|
self.errored: bool = False
|
|
|
|
# PARSE BANDS
|
|
def_split = turing_machine_def.replace(' ', '').replace('\n', '').lower().split(';')
|
|
self.band_num = int(def_split[0])
|
|
|
|
# PARSE STATES
|
|
self.state_start = def_split[1]
|
|
self.state_current = def_split[1]
|
|
self.state_accept = def_split[2]
|
|
self.state_reject = def_split[3]
|
|
|
|
def_split_truncated = def_split[4:]
|
|
|
|
# PARSE RULES
|
|
for x in def_split_truncated:
|
|
if not x: continue
|
|
|
|
rule_current = x.split(',')
|
|
tmp = rule_current[1].split('->')
|
|
rule_current[1] = tmp[0]
|
|
rule_current.insert(2, tmp[1])
|
|
|
|
self.rules.append(rule_current)
|
|
|
|
|
|
def turing_run(self) -> None:
|
|
'''Runs the TM without giving the option to step through manually.'''
|
|
while not self.turing_finished():
|
|
self.turing_step()
|
|
if self.errored: return
|
|
|
|
|
|
def turing_step(self) -> bool:
|
|
'''Steps through the TM one rule at a time. A step is changing
|
|
the value of the current element and moving the band by one.
|
|
Returns whether the TM has finished running or has an empty band.'''
|
|
if len(self.band) == 0:
|
|
return True
|
|
|
|
# Add blank if current location is out of bounds and adjust location
|
|
if self.band_current < 0:
|
|
self.band.insert(0, '_')
|
|
self.band_current = 0
|
|
|
|
if self.band_current == len(self.band):
|
|
self.band.append('_')
|
|
|
|
for rule in self.rules:
|
|
# Skip if rule does not apply to current state
|
|
if not rule[0] == self.state_current: continue
|
|
# Skip if rule does not apply to current band element
|
|
if not rule[1] == self.band[self.band_current]: continue
|
|
|
|
# Set band element according to rule
|
|
self.band[self.band_current] = rule[3]
|
|
# Set current state according to rule
|
|
self.state_current = rule[2]
|
|
|
|
# Move band according to rule
|
|
if rule[4] == '<':
|
|
self.band_current -= 1;
|
|
if rule[4] == '>':
|
|
self.band_current += 1;
|
|
|
|
self.rule_used = ( rule[0] + ', ' +
|
|
rule[1] + ' -> ' +
|
|
rule[2] + ', ' +
|
|
rule[3] + ', ' +
|
|
rule[4])
|
|
|
|
break
|
|
|
|
return self.turing_finished()
|
|
|
|
|
|
def turing_finished(self) -> bool:
|
|
'''Returns whether the TM is in accepting state, rejecting state or has
|
|
halted because no applicable rules are left.'''
|
|
return ( self.state_current == self.state_accept or
|
|
self.state_current == self.state_reject or
|
|
self.errored )
|
|
|
|
|
|
def turing_accepted(self) -> bool:
|
|
'''Returns whether the TM, with the given input, has reached accepted state.'''
|
|
return self.state_current == self.state_accept
|
|
|
|
|
|
def turing_reset(self) -> None:
|
|
'''Resets current state to start state and band location to zero.'''
|
|
self.state_current = self.state_start
|
|
self.band_current = 0
|
|
|
|
|
|
def get_rules(self) -> list:
|
|
return self.rules
|
|
|
|
def get_rule_used(self) -> str:
|
|
return self.rule_used
|
|
|
|
def get_band(self) -> str:
|
|
return (''.join(self.band)).replace('_', '')
|
|
|
|
def get_band_context(self, context: int) -> str:
|
|
'''Returns context chars to the left and right of the current element as well as the element.'''
|
|
ret = ""
|
|
for i in range(self.band_current - context, self.band_current + context + 1):
|
|
if i < 0:
|
|
ret += "_ "
|
|
elif i+1 > len(self.band):
|
|
ret += "_ "
|
|
else:
|
|
ret += f"{self.band[i]} "
|
|
|
|
return ret.rstrip()
|
|
|
|
def get_band_current_element(self) -> str:
|
|
if self.band_current < 0 or self.band_current == len(self.band):
|
|
return '_'
|
|
return self.band[self.band_current]
|
|
|
|
def get_state_start(self) -> str:
|
|
return self.state_start
|
|
|
|
def get_state_current(self) -> str:
|
|
return self.state_current
|
|
|
|
def get_state_accept(self) -> str:
|
|
return self.state_accept
|
|
|
|
def get_state_reject(self) -> str:
|
|
return self.state_reject
|
|
|
|
def get_has_errored(self) -> bool:
|
|
return self.errored
|
|
|
|
|
|
def set_band(self, input: str):
|
|
self.band = list(input)
|
|
|
|
def redefine(self, turing_machine_def: str):
|
|
self.__init__(turing_machine_def)
|
|
|
|
|
|
|
|
def test():
|
|
tm = TuringMachine(''' 1; q0; q3; q4;
|
|
q0, 0 -> q0, 0, > ;
|
|
q0, 1 -> q0, 1, > ;
|
|
q0, _ -> q1, _, < ;
|
|
q1, 0 -> q2, 1, < ;
|
|
q1, 1 -> q1, 0, < ;
|
|
q1, _ -> q3, 1, - ;
|
|
q2, 1 -> q2, 1, < ;
|
|
q2, 0 -> q2, 0, < ;
|
|
q2, _ -> q3, _, >
|
|
''')
|
|
|
|
tm.set_band("1011")
|
|
tm.turing_run()
|
|
if tm.get_band() == "1100":
|
|
print("Successfull")
|
|
else:
|
|
print("Failed")
|
|
|