Accepted Language & Decided Language

A TM accepts a language if it enters into a final state for any input string w. A language is recursively enumerable (generated by Type-0 grammar) if it is accepted by a Turing machine.

A TM decides a language if it accepts it and enters into a rejecting state for any input not in the language. A language is recursive if it is decided by a Turing machine.

There may be some cases where a TM does not stop. Such TM accepts the language, but it does not decide it.

Designing a Turing Machine

The basic guidelines of designing a Turing machine have been explained below with the help of a couple of examples.

Example 1

Design a TM to recognize all strings consisting of an odd number of α’s.

Solution

The Turing machine M can be constructed by the following moves −

• Let q₁ be the initial state.

• If M is in q₁; on scanning α, it enters the state q₂ and writes B (blank).

• If M is in q₂; on scanning α, it enters the state q₁ and writes B (blank).

• From the above moves, we can see that M enters the state q₁ if it scans an even number of α’s, and it enters the state q₂ if it scans an odd number of α’s. Hence q₂ is the only accepting state.

Hence,

M = {{q₁, q₂}, {1}, {1, B}, δ, q₁, B, {q₂}}

where δ is given by −

Example 2

Design a Turing Machine that reads a string representing a binary number and erases all leading 0’s in the string. However, if the string comprises of only 0’s, it keeps one 0.

Solution

Let us assume that the input string is terminated by a blank symbol, B, at each end of the string.

The Turing Machine, M, can be constructed by the following moves −

• Let q₀ be the initial state.

• If M is in q₀, on reading 0, it moves right, enters the state q₁ and erases 0. On reading 1, it enters the state q₂ and moves right.

• If M is in q₁, on reading 0, it moves right and erases 0, i.e., it replaces 0’s by B’s. On reaching the leftmost 1, it enters q₂ and moves right. If it reaches B, i.e., the string comprises of only 0’s, it moves left and enters the state q₃.

• If M is in q₂, on reading either 0 or 1, it moves right. On reaching B, it moves left and enters the state q₄. This validates that the string comprises only of 0’s and 1’s.

• If M is in q₃, it replaces B by 0, moves left and reaches the final state q_f.

• If M is in q₄, on reading either 0 or 1, it moves left. On reaching the beginning of the string, i.e., when it reads B, it reaches the final state q_f.

Hence,

M = {{q₀, q₁, q₂, q₃, q₄, q_f}, {0,1, B}, {1, B}, δ, q₀, B, {q_f}}

where δ is given by −