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:

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:

aabbaabb

Transition table:

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