This is the second 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 of a form w = xx
. Idea is: first I add delimiters ^
to the word boundary. Next, I use $
to cut one character at a time from the prefix and from the suffix of the word. Finally, I know where is the center of the word, so I can compare characters one by one.
States:
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 |
q0 - start q1 - a in buffer q2 - b in buffer q3 - aa in buffer q4 - ab in buffer q5 - ba in buffer q6 - bb in buffer q7 - last a in buffer q8 - last b in buffer q9 - time to place $ q10 - time to place ^ q11 - looking for $ to the left to push q12 - getting first character to the left q13 - rewriting a with $ while going left q14 - rewriting b with $ while going left q15 - going to the left boundary ^ to rewrite q16 - going to the left boundary ^ to compare words q17 - looking for $ to the right to push q18 - getting first character to the right q19 - rewriting a with $ while going right q20 - rewriting b with $ while going right q21 - going to the right boundary ^ to rewrite q22 - comparing from the left ^ q23 - looking for a in the word on the right q24 - looking for b in the word on the right q25 - have the word center, looking a on the right q26 - have the word center, looking b on the right q_fail - failure q_ok - word is correct |
The input looks like this:
1 |
aabbaabb |
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
a,q0,^,q1,R b,q0,^,q2,R a,q1,$,q3,R b,q1,$,q4,R a,q2,$,q5,R b,q2,$,q6,R a,q3,a,q3,R b,q3,a,q4,R .,q3,a,q7,R a,q4,a,q5,R b,q4,a,q6,R .,q4,a,q8,R a,q5,b,q3,R b,q5,b,q4,R .,q5,b,q7,R a,q6,b,q5,R b,q6,b,q6,R .,q6,b,q8,R .,q7,a,q9,R .,q8,b,q9,R .,q9,$,q10,R .,q10,^,q11,L a,q11,a,q11,L b,q11,b,q11,L $,q11,$,q12,L a,q12,$,q13,R b,q12,$,q14,R $,q12,$,q16,L $,q13,a,q15,L $,q14,b,q15,L a,q15,a,q15,L b,q15,b,q15,L $,q15,$,q15,L ^,q15,^,q17,R a,q17,a,q17,R b,q17,b,q17,R $,q17,$,q18,R a,q18,$,q19,L b,q18,$,q20,L $,q18,$,q_fail,L $,q19,a,q21,R $,q20,b,q21,R a,q21,a,q21,R b,q21,b,q21,R $,q21,$,q21,R ^,q21,^,q11,L a,q16,a,q16,L b,q16,b,q16,L $,q16,$,q16,L ^,q16,^,q22,R a,q22,^,q23,R b,q22,^,q24,R $,q22,$,q_ok,R a,q23,a,q23,R b,q23,b,q23,R $,q23,$,q25,R a,q24,a,q24,R b,q24,b,q24,R $,q24,$,q26,R $,q25,$,q25,R a,q25,$,q16,L b,q25,b,q_fail,R $,q26,$,q26,R a,q26,a,q_fail,R b,q26,$,q16,L |