This is the third 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 if given word w is a palindrome. First, we add delimiters at the beginning and at the end. Next, we check first character from the left, go to the end and check if the last character matches. Then we go to the beginning and repeat.
States:
|
1 2 3 4 5 6 7 8 9 10 11 |
q0 - start q1 - a in buffer q2 - b in buffer q3 - add $ at the end q4 - return to begin q5 - checking first character from the left q6 - going to the end with a q7 - going to the end with b q8 - checking a as the last character q9 - checking b as the last character q10 - success |
The input looks like this:
|
1 |
abba |
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 27 28 29 30 31 32 33 34 |
a,q0,$,q1,R b,q0,$,q2,R a,q1,a,q1,R b,q1,a,q2,R .,q1,a,q3,R a,q2,b,q1,R b,q2,b,q2,R .,q2,b,q3,R .,q3,$,q4,L a,q4,a,q4,L b,q4,b,q4,L $,q4,$,q5,R a,q5,$,q6,R b,q5,$,q7,R $,q5,$,q10,R a,q6,a,q6,R b,q6,b,q6,R $,q6,$,q8,L a,q7,a,q7,R b,q7,b,q7,R $,q7,$,q9,L a,q8,$,q4,L $,q8,$,q10,L b,q9,$,q4,L $,q9,$,q10,L |