Simple turing machine made in python The sample automata accepts strings from: L = {a^n . b^(2n) : n >= 1}
Example: abb (accepts) aabbbb (accepts) aab (don't accept)
s0 -> q1 ? a : * ; R | |
s0 -> s0 ? * : * ; R | |
s0 -> q4 ? + : + ; R | |
q1 -> q2 ? b : + ; R | |
q1 -> q1 ? a : a ; R | + : + ; R | |
q2 -> q3 ? b : + ; L | |
q3 -> q3 ? * : * ; L | a : a ; L | + : + ; L | |
q3 -> s0 ? B : B ; R | |
q4 -> q4 ? + : + ; R | |
q4 -> f5 ? B : B ; L |
class State: | |
def __init__(self, state): | |
self.state = state | |
self.transitions = {} | |
def add_transition(self, char, **kwargs): | |
# replace, direction, destin | |
self.transitions[char] = kwargs | |
D = {} | |
if __name__ == '__main__': | |
f = open('sample') | |
for line in f.read().splitlines(): | |
line = line.replace(' ' , '') | |
# get state | |
st = line.split('->')[0] | |
# get destin and transitions | |
dest, tr = line.split('->')[1].split('?') | |
# create State | |
if st not in D.keys(): | |
S = State(st) | |
else: | |
S = D[st] | |
# get each transition from transitions | |
all_tr = tr.split('|') | |
for t in all_tr: | |
# char | |
c = t.split(':')[0] | |
# replace, direction, destin | |
r, d = t.split(':')[1].split(';') | |
S.add_transition(c, replace=r, direction=d, destin=dest) | |
D[st] = S | |
tape = ['B']*3 + list(input()) + ['B']*3 | |
pointer = 3 | |
# initial state | |
curr_state = D['s0'].transitions | |
while True: | |
# current char | |
curr_char = tape[pointer] | |
# current state transitions | |
state_tr = curr_state[curr_char] | |
# replace char | |
tape[pointer] = state_tr['replace'] | |
# update pointer | |
if state_tr['direction'] == 'R': | |
pointer += 1 | |
else: | |
pointer -= 1 | |
# update current state | |
if state_tr['destin'][0] == 'f': | |
print('accept!') | |
break | |
elif state_tr['destin'] not in D.keys(): | |
print('not accept!') | |
break | |
else: | |
curr_state = D[state_tr['destin']].transitions | |
print(tape[3:-3]) |