Turing Machine for language { www | w ∈ {a, b} }
Prerequisite – Turing Machine
Design a Turing Machine for a string which contains exactly 3 repetitions of w consecutively.
Approach Used :
First, we will find the position of separation of the first w from the second w.
Now, we will match the first and second w. If both get, matched then the second w string will be converted to a string of $.
Then, we will match the first and third w. If both get, matched then the third w string will be converted to a string of $. If the string reaches the Halt state H, then it gets accepted.
Example –
Input: ababab Output: Accepted Input: abbabbabb Output: Accepted Input: ^ (Empty string) Output: Accepted Input: aba Output: Not accepted
Step-1:
If the symbol is $, replace it by $ and move right.
Go to state Q1 and step 2.
Step-2:
If the symbol is a, replace it by A and move right, or
If the symbol is b, replace it by B and move right.
Go to state Q2 and step 3.
————————————————-
If the symbol is A, replace it by A and move left, or
If the symbol is B, replace it by B and move left.
Go to state Q6 and step 7.
————————————————-
If the symbol is $, replace it by $, and the string is accepted.
Go to final state H.
Step-3:
If the symbol is a, replace it by a and move right, remain on the same state, or
If the symbol is b, replace it by b and move right, remain on the same state.
————————————————
If the symbol is A replace it by A and move left, or
If the symbol is B replace it by B and move left, or
If the symbol is $ replace it by $ and move left.
Go to state Q3 and step 4.
Step-4:
If the symbol is a replace it by A and move left, or
If the symbol is b replace it by B and move left,
Go to state Q4 and step 5
Step-5:
If the symbol is a replace it by A and move left, or
If the symbol is b replace it by B and move left,
Go to state Q5 and step 6
Step-6:
If the symbol is a, replace it by a and move left, remain on the same state, or
If the symbol is b, replace it by b and move left, remain on the same state.
————————————————
If the symbol is A, replace it by A and move right, or
If the symbol is B, replace it by B and move right, or
Go to state Q1 and step 2.
Step-7:
If the symbol is A, replace it by a and move left, remain on the same state, or
If the symbol is B, replace it by b and move left, remain on the same state
————————————————-
If the symbol if $, replace it by $ and move right.
Go to state Q7 and step 8.
Step-8:
If the symbol is a, replace it by A and move right.
Go to state Q9 and step 10.
————————————————–
If the symbol is b, replace it by B and move right.
Go to state Q8 and step 9.
————————————————–
If the symbol is $, replace it by $ and move left.
Go to state Q11 and step 12.
Step-9:
If the symbol is a, replace it by a and move right, remain on the same state, or
If the symbol is b, replace it by b and move right, remain on the same state, or
If the symbol is $, replace it by $ and move right, remain on the same state
————————————————–
If the symbol is B, replace it by $ and move left.
Go to state Q10 and step 11.
Step-10:
If the symbol is a, replace it by a and move right, remain on the same state, or
If the symbol is b, replace it by b and move right, remain on the same state, or
If the symbol is $, replace it by $ and move right, remain on the same state.
————————————————–
If the symbol is A, replace it by $ and move left.
Go to state Q10 and step 11.
Step-11:
If the symbol is a, replace it by a and move left, remain on the same state, or
If the symbol is b, replace it by b and move left, remain on the same state, or
If the symbol is $, replace it by $ and move left.
————————————————–
If the symbol is A, replace it by A and move right, or
If the symbol is B, replace it by B and move right.
Go to state Q7 and step 8.
Step-12:
If the symbol is A, replace it by a and move left, remain on the same state, or
If the symbol is B, replace it by b and move left, remain on the same state.
————————————————–
If the symbol is $, replace it by $ and move right.
Go to state Q12 and step 13.
Step-13:
If the symbol is a, replace it by A and move right.
Go to state Q14 and step 15.
————————————————–
If the symbol is b, replace it by B and move right.
Go to state Q13 and step 14.
————————————————–
If the symbol is $, replace it by $, and the string is accepted.
Go to final state H.
Step-14:
If the symbol is a, replace it by a and move right, remain on the same state, or
If the symbol is b, replace it by b and move right, remain on the same state, or
If the symbol is $, replace it by $ and move right, remain on the same state.
————————————————–
If the symbol is B, replace it by $ and move left.
Go to state Q15 and step 16.
Step-15:
If the symbol is a, replace it by a and move right, remain on the same state, or
If the symbol is b, replace it by b and move right, remain on the same state, or
If the symbol is $, replace it by $ and move right, remain on the same state.
————————————————–
If the symbol is A, replace it by $ and move left.
Go to state Q15 and step 16.
Step-16:
If the symbol is a, replace it by a and move left, remain on the same state, or
If the symbol is b, replace it by b and move left, remain on the same state, or
If the symbol is $, replace it by $ and move left.
————————————————–
If the symbol is A, replace it by A and move right, or
If the symbol is B, replace it by B and move right.
Go to state Q12 and step 13.
Meaning of symbols-
R- move right L- move left a- character a b- character b A- character A B- character B
Example:
We have to test the Turing machine for a string “ababab”.
-> $ababab$ -> $Ababab$ -> $AbabaB$ ->$AbabAB$ -> $ABabAB$ -> $ABaBAB$ -> $ABABAB$ -> $AbABAB$ -> $abABAB$ -> $AbABAB$ -> $Ab$BAB$ -> $AB$BAB$ -> $AB$$AB$ -> $Ab$$AB$ -> $ab$$AB$ -> $Ab$$AB$ -> $Ab$$$B$ -> $AB$$$B$ -> $AB$$$$$ (Accepted)
Contact Us