Question

Show that the single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.

Short answer

Answer

It can be shown that the single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.

Step-by-step solution

Explain Turing Machine

Turing machine is the computational model that has an unlimited memory. It has a tape that can read and write symbols as input.

Show that the single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.

Consider the single-tape Turing Machine S that only reads symbols and cannot write on the portion of the tape that has an input string.

Consider the two events that happen in S, in-event and out-event. In the in-event, tape head moves to the input portion. In the out-event, that tape head moves to the portion on the right of the cell x.

Consider the state, $q_1$in S , on entering the non-input portion. The following are the two possibilities.

Case 1:never enters the non-input portion

If accepts X , assign $q_x$=$q_{accept}$

If S rejects, $q_x=q_{reject}$

For any that belongs to Q (set of inputs), such that $f_x\left(q\right)=q\text{'}.$

Thus, the S is in the state that undergoes in-event and then out-event will change S is q'

Case 2: S never enters the non-input portion again,

• If S accepts x in input portion, assign $f_x\left(q\right)=q_{accept}$
• If S rejects,$f_x\left(q\right)=q_{reject}$

• Consider two strings, x and y and if x=y for all q , then $f_x\left(q\right)=f_y\left(q\right)$.

  Thus, S accepts xz if ana only if it accepts yz

  
  

  Thus, the number of indistinguishable strings are finite. By theorem “Myhill-Nerode theorem”, the language recognized by is regular.

  
  

  Therefore, It has been shown that the single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.

  
  

.

.