This is the fifth part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition
Today we check whether a string has exactly twice as many ones as zeroes.
States:
q0 - looking for the beginning q1 - looking for 0 q2 - have 0, looking for end q3 - looking for first 1 q4 - looking for second 1 q5 - checking for no 1 qyes - matches
The input looks like this:
$011$
Transition table:
$,q0,$,q1,R ^,q0,^,q0,L 0,q0,0,q0,L 1,q0,1,q0,L 0,q1,^,q2,R 1,q1,1,q1,R ^,q1,^,q1,R $,q1,$,q5,L 0,q2,0,q2,R 1,q2,1,q2,R ^,q2,^,q2,R $,q2,$,q3,L 0,q3,0,q3,L 1,q3,^,q4,L ^,q3,^,q3,L 0,q4,0,q4,L 1,q4,^,q0,L ^,q4,^,q4,L ^,q5,^,q5,L $,q5,$,qyes,R