Turing Machine For a^Nb^Nc^N

Design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0. Given language (L = aNbNcN) will generate an equal number of a’s, b’s, and c’s. So, consider an input tap that holds L=aabbcc as given below,

Turing Machine input tape for the language L = a^Nb^Nc^N where N>0

R/W Head Movement For Language a^Nb^Nc^N (aNbNcN)

Following is the R/W head movement for language a^bb^nc^n.

Read write head movement in tap for Turing Machine a^Nb^Nc^N

Algorithm For Language a^Nb^Nc^N (aNbNcN)

Following is the algorithm for the language a^bb^nc^n in the Turing Machine.

  • Step 01: Change “a” to X, after reading “a”.
  • Step 02: Move Right to the First “b”. If you find “b”, change “b” to “Y”; otherwise, reject the language.
  • Step 03: Move Right to the First “c.” If “c” is found, then Change “c” to “Z”; otherwise, reject the language.
  • Step 04: Move Left to Leftmost “a”
  • Step 05: Repeat Steps 01 to 04 until no more “a,” b,” and “c” remain in the input tape.

Let’s construct a Turing Machine for the Language L= aabbcc.

According to Step 01, Change “a” to “X”

  • State change from q0 to q1
  • Read/Write Head moves toward right.

The following diagram shows the input tape and Turing machine behavior.

Step number 1 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

According to Step 02, change the first right b to Y.

  • State change from q1 to q2
  • Read/Write Head moves toward the right side

The following diagram shows the input tape and Turing machine behavior.

Step number 2 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

According to Step 03, change the first right “c” to “Z”

  • State change from q2 to q3
  • Read/Write Head moves toward Left.

The following diagram shows the input tape and Turing machine behavior.

Step number 3 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

Now repeat steps 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”

The following diagram shows the input tape and Turing machine behavior.

Step number 4 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

Step 05: Repetition from Step 01 to Step 04 starts

According to Step 01, replace the leftmost “a” with “X”.

Step number 5 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

Again, According to Step 02, replace the first right “b” with “Y”.

Step number 6 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

According to Step 03, change the first right “c” to “Z”. The following diagram shows the input tape and Turing machine behavior.

Step number 7 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

At this point, all “a”, “b”, and “c” are replaced with “X”, “Y”, and “Z” respectively.

The Read/Write Head points X at q0 and moves toward the right. So, to reach the special symbol “$,” consume all “X”, “Y”, and “Z”. As below.

Step number 8 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

Completion of step 05 for L = a^Nb^Nc^N

Finally, using the special symbol “$”, the R/W head moves toward the last symbol of the given language as given below, and the language is accepted.

Step number 9 to design a Turing Machine that recognizes the language L = a^Nb^Nc^N where N>0

Note: After reaching the final state, the R/W head will stop moving, and we can represent it with the “N” symbol. The final transition may look like the following:

δ($,$,N)