Skip to content

Instantly share code, notes, and snippets.

@douglas-vaz
Created October 14, 2012 13:36
Show Gist options
  • Save douglas-vaz/3888619 to your computer and use it in GitHub Desktop.
Save douglas-vaz/3888619 to your computer and use it in GitHub Desktop.
Turing Machine to accept the language {0^m1^m: m >= 1}
print "Enter string"
inp = list(raw_input()) + [' ']
R, L = lambda f:f+1, lambda f:f-1
state, i = 0, 0
machine = [{'0':[1,'X',R], 'Y':[3,'Y',R]}, {'0':[1,'0',R], 'Y':[1,'Y',R], '1':[2,'Y',L]}, {'Y':[2,'Y',L], '0':[2,'0',L], 'X':[0,'X',R]},{'Y':[3,'Y',R], ' ':[4,' ',R]},{}]
while state != 4:
print inp[i],': State = ',state,
try:
state,inp[i],i = machine[state].get(inp[i])[0], machine[state].get(inp[i])[1], machine[state].get(inp[i])[2](i)
print '->',state, "".join(inp)
except TypeError:
break
if state == 4:
print "\nString accepted"
else:
print "\nString not accepted"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment