Turing Machine For a^Nb^Nc^N
Design a Turing Machine which recognizes the language L = aNbNcN where N>0.
Given language (L = aNbNcN) will generate equal number of a’s, b’s and c’s. So, consider a input-tap which hold L=”aabbcc” as given below
Algorithm For Language aNbNcN
Algorithm for above language in Turing Machine to Accept is given below
- Step 01: Change “a” to “X”
- Step 02: Move Right to First “b”. If “b” found then Change “b” to “Y” otherwise simply reject the language.
- Step 03: Move Right to First “c”. If “c” found then Change “c” to “Z” otherwise simply reject the language.
- Step 04: Move Left to Leftmost “a”
- Step 05: Repeat Step 01 to 04 until no more “a”, “b” and “c” remain in the input tape.
Let construct Turing Machine for Language “aabbcc”.
According to Step 01, Change “a” to “X”.
- State change from q0 to q1
- Read/Write Head moves toward Right.
Input tap and Turing Machine behavior is given below
According to Step 02, change first right “b” to “Y”.
- State change from q1 to q2
- Read/Write Head moves toward Right.
Input tap and Turing Machine behavior is given below
According to Step 03, change first right “c” to “Z”.
- State change from q2 to q3
- Read/Write Head moves toward Left.
Input tap and Turing Machine behavior is given below
Now repeat the step 01 to 04 to replace all “a”, “b” and “c” with “X”, “Y” and “Z” respectively. |
According to Step 04 Move Left to Leftmost “a”, Input tap and Turing Machine behavior is given below
Again According to Step 01, replaces leftmost “a” with “X”.
Again According to Step 02, replaces first right “b” with “Y”.
According to Step 03, change first right “c” to “Z”. Input tap and Turing Machine behavior is given below
At this point all “a”, “b” and “c” are replaced with “X”, “Y” and “Z” respectively. |
As the Read/Write Head is pointing X at q0 and Moving toward right. So, to reach at special symbol “$” consume all “X”, “Y” and “Z”. As below
Final, by using special symbol “$”, the R/W head moves toward the last symbol of given language as given below and language is accepted.