I was going through the automata text by Peter Linz where I came across the construction below.

To show the converse, we describe how any Turing machine can be mimicked by an unrestricted grammar. We are given a Turing machine $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ and want to produce a grammar $G$ such that $L (G) = L (M)$. The idea behind the construction is relatively simple, but its implementation becomes notationally cumbersome.

Since the computation of the Turing machine can be described by the sequence of instantaneous descriptions

$$q_0w \vdash^* xq_fy, \tag {11.3}$$

we will try to arrange it so that the corresponding grammar has the property that

$$q_0w \Rightarrow^* xq_fy, \tag {11.4}$$

if and only if $(11.3)$ holds. This is not hard to do; what is more difficult to see is how to make the connection between $(11.4)$ and what we really want, namely, $$S \Rightarrow ^* w$$

for all $w$ satisfying $(11.3)$. To achieve this, we construct a grammar which, in broad outline, has the following properties:

  1. $S$ can derive $q_0w$ for all $w \in \Sigma^+$.
  2. $(11.4)$ is possible if and only if $(11.3)$ holds.
  3. When a string $xq_fy$ with $q_f \in F$ is generated, the grammar transforms this string into the original $w$.

The complete sequence of derivations is then

$$S \Rightarrow^* q_0w \Rightarrow^* xq_fy \Rightarrow^* w \tag {11.5} $$

The third step in the above derivation is the troublesome one. How can the grammar remember $w$ if it is modified during the second step? We solve this by encoding strings so that the coded version originally has two copies of $w$. The first is saved, while the second is used in the steps in $(11.4)$. When a final configuration is entered, the grammar erases everything except the saved $w$.

To produce two copies of $w$ and to handle the state symbol of $M$ (which eventually has to be removed by the grammar), we introduce variables $V_{ab}$ and $V_{aib}$ for all $a \in \Sigma \cup \{\square \}$, $b \in \Gamma$, and all $i$ such that $qi \in Q$. The variable $V_{ab}$ encodes the two symbols $a$ and $b$, while $V_{aib}$, encodes $a$ and $b$ as well as the state $q_j$.

The first step in $(11.5)$ can be achieved (in the encoded form) by $$S \rightarrow V_{\square\square}S | SV_{\square\square}|T, \tag{11.6}$$ $$T -\rightarrow TV_{aa}|V_{a0a}, \tag{11.7}$$

for all $a \in \Sigma$. These productions allow the grammar to generate an encoded version of any string $q_0w$ with an arbitrary number of leading and trailing blanks.

For the second step, for each transition

$$\delta (q_i,c) = (q_j,d,R)$$

of $M$, we put into the grammar productions

$$V_{aic}V_{pq} \rightarrow V_{ad}V_{pjq}, \tag{11.8}$$

for all $a, p \in \Sigma \cup \{\square \}$, $q \in \Gamma$. For each

$$\delta (q_i,c) = (q_j,d,L)$$

of $M$, we include in G

$$V_{pq}V_{aic} \rightarrow V_{pjq}V_{ad}, \tag{11.9}$$

for all $a, p \in \Sigma \cup \{\square \}$, $q \in \Gamma$.

If in the second step, $M$ enters a final state, the grammar must then get rid of everything except $w$, which is saved in the first indices of the $V's$. Therefore, for every $q_j \in F$, we include productions

$$V_{ajb}\rightarrow a, \tag{11.10}$$

for all $a \in \Sigma \cup \{\square\}$, $b \in \Gamma$. This creates the first terminal in the string, which then causes a rewriting in the rest by

$$cV_{ab} \rightarrow ca, \tag{11.11}$$ $$V_{abc} \rightarrow ac, \tag{11.12}$$

for all $a \in \Sigma \cup \{\square\}$, $b \in \Gamma$. We need one more special production $$\square\rightarrow A. \tag{11.13}$$

This last production takes care of the case when $M$ moves outside that part of the tape occupied by the input $w$. To make things work in this case, we must first use $(11.6)$ and $(11.7)$ to generate

$$ \square... \square q_0w\square ...\square$$,

representing all the tape region used. The extraneous blanks are removed at the end by $(11.13)$.

Though the author says that the idea behind the construction is relatively simple, but the notational convention and the length of the process is blowing me up. Can anyone explain the intuition or the basic idea in simple words and somehow simplify the construction used.

I am having difficulty in grasping it...

Here there is an answer, but it seems quite different to me and the general $TM$ here also uses non input symbols.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.