Turing Machine Example

In this class, We discuss Turing Machine Example.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of Turing Machine construction. Click Here.

The language L1 = {0ⁿ1ⁿ where n >=1}

Σ = { 0, 1} and τ = {0, 1, X, Y, B}

The below diagram shows the sample input in the tape memory.

The sample input is 000111.

The turing machine starts from the starting of the input.

Logic:

First, we take the symbol zero and convert it to ‘X’.

We need to find the first one for the first zero and convert it to ‘Y’.

Similarly, we need to move back, identify the second zero, and convert it to ‘X’.

We need to identify the second ‘1’ for the second zero.

If we find equal zero’s and one’s, we must accept the string.

First, we convert the zero to ‘X’, and move right.

Next, move right till we find 1.

After finding one, we convert to ‘Y’ and move left.

We move left till we find ‘X’ and move right.

Now the second zero is identified. 

We repeat the above conversion pro

Example:

The below diagram shows the not accepting example string.

The input string is 00111.

We have two zero’s and three ones.

We need to check the extra one’s condition.

The below diagram shows the Turing Machine for the language L1.

We start with state q0.

On the state q0, if we find the input symbol 0, we change to ‘X’ and move right. And to state q1.

We use the state q1 to move right till we find ‘1’.

On the state q1, if we see input 0 or Y, we keep the same and move right.

On the state q1, if we see input symbol one, we move left and move to state q2.

We use the state q2 to move left till we find ‘X’.

On the state q2, if we see the input symbol ‘Y’ or 0, we move left till we find ‘X’.

On the state q2, if we see the input symbol ‘X’, we move right and to state q0.

On the state q0, if we see the input symbol ‘Y’, the zero’s are completed.

After completing zeroes we need to check for extra one’s.

On state q0, if we see input symbol ‘Y’, we move to state q3.

We use state q3 to move right to check for one’s.

If we find blank, the input is accepted.