# Turing Machine For 0^N1^N

Design a Turing Machine which recognizes the language L = 0^{N}1^{N }where N>0.

Given language (L = 0^{N}1^{N}) will generate equal number of 0’s and 1’s. So, consider a input-tap which hold L=”000111” as given below

__Algorithm For Language (L = 0__^{N}1^{N})

__Algorithm For Language (L = 0__

^{N}1^{N})Algorithm for above language in Turing Machine to Accept is given below

**Step 01:**Change “0” to “X”**Step 02:**Move Right to First “1”.If no “1” found then simply reject the language**Step 03:**Change “1” to “Y”**Step 04:**Move Left to Leftmost “0”**Step 05:**Repeat Step 01 to 04 until no more “0” and “1” remain in the input tape.

Let construct Turing Machine for a string “000111” of given Language.

**According to Step 01, For the first Input “0”**

- Transition goes from initial state (q0) to state (q1).
- The first symbol “0” of input tape is updated to “X”
- Read/Write Head Move to One position Right

**According to Step 2 and 3 ,R/W Head Move to Right To update first “1” in right side of input Tape**

- Transition goes from state (q1) to state (q2).
- The symbol “1” of input tape is updated to “Y”
- R/W Head Move one Position Left to update Leftmost “0” in the next.

At q1, transition will remain in same state for input “0” as given below

**According To Step 4 and 01, Move Left to Leftmost “0” and update it to “X”, As **

- Transition goes from state (q2) to state (q1) for input “X”
- The Leftmost “0” of input tape is updated to “X”
- After Update Leftmost “0” to “X”, R/W head move to Right for upcoming “1” updating.

**Again, According to Step 2 and 3, R/W Head Move to Right To update first “1” in right side of input tape.**

Input tape and Turing machine diagram explain the detail in below

**Again According To Step 4 and 01, Move Left to Leftmost “0” and update it to “X”, As given below**

**Again, According to Step 2 and 3 R/W Head Move to Right To update first “1” in right side of input tape as explain below**

**At this point, **

- all the 0’s and 1’s are updated with X and Y respectively in input tape.
- Current State is q2 and R/W head is moving toward Left of each input “Y”
- As X input occur, state goes to q0 and R/W Head moves toward Right.
- By consuming all input “Y”, state will be q3.
- As first special symbol “$” occur, state goes to final state (q4) and R/W head will point the last symbol of considered language.

**Hence, language Accepted as given below**

**Note**: For Special symbol (“$”) at state q0, language is accepted.