Simple implementation of a turing machine

README.md

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)

sample

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

turing.py

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])