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:
|
1 2 3 4 5 6 7 |
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:
|
1 |
$011$ |
Transition table:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
$,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 |