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 _{1}** be the initial state.

· If **M** is in **q _{1}**; on scanning α, it enters the state

**q**and writes

_{2}**B**(blank).

· If **M** is in **q _{2}**; on scanning α, it enters the state

**q**and writes

_{1}**B**(blank).

· From the above moves, we can see that **M** enters the state **q _{1}** if it scans an even number of α’s, and it enters the state

**q**if it scans an odd number of α’s. Hence

_{2}**q**is the only accepting state.

_{2}Hence,

M = {{q_{1}, q_{2}}, {1}, {1, B}, δ, q_{1}, B, {q_{2}}}

where δ is given by −

Tape alphabet symbol | Present State ‘q_{1}’ | Present State ‘q_{2}’ |

α | BRq_{2} | BRq_{1} |

**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 _{0}** be the initial state.

· If **M** is in **q _{0}**, on reading 0, it moves right, enters the state

**q**and erases 0. On reading 1, it enters the state

_{1}**q**and moves right.

_{2}· If **M** is in **q _{1}**, 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

_{2}**q**.

_{3}· If **M** is in **q _{2}**, 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.

_{4}· If **M** is in **q _{3}**, it replaces B by 0, moves left and reaches the final state

**q**.

_{f}· If **M** is in **q _{4}**, 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_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{f}}, {0,1, B}, {1, B}, δ, q_{0}, B, {q_{f}}}

where δ is given by −

Tape alphabet symbol | Present State ‘q_{0}’ | Present State ‘q_{1}’ | Present State ‘q_{2}’ | Present State ‘q_{3}’ | Present State ‘q_{4}’ |

0 | BRq_{1} | BRq_{1} | ORq_{2} | – | OLq_{4} |

1 | 1Rq_{2} | 1Rq_{2} | 1Rq_{2} | – | 1Lq_{4} |

B | BRq_{1} | BLq_{3} | BLq_{4} | OLq_{f} | BRq_{f} |

Comments are closed.