According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine.

How do I indeed do that and convert the Turing machine the recognizes language $L$ into an unrestricted grammar? I have tried replacing transition rules with grammar rules, but a Turing machine can have many different configurations of states as well...


We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at.

The second crucial idea is that we have to reverse the process: TMs take the word as input and convert it to $1$ or $0$, or they don't terminate. The grammar, however, has to generate the word. Luckily, grammars are inherently non-deterministic, so we can just let it "guess" where the accepting $1$ came from; all words that cause the TM to accept can be generated then.

Let $\cal{Q} = \{Q_0,\dots,Q_k\}$ the set of state-nonterminals; w.l.o.g. let $Q_0$ be the starting-state-nonterminal and $\cal{Q}_F \subseteq \cal{Q}$ the set of accepting-states-nonterminals. First, we need starting rules that generate all possible accepting configurations:

$\qquad \displaystyle S \to \#1Q_f\# \qquad$ for all $Q_f \in \cal{Q}_F$.

Similarly, we terminate when we "reach" the starting state in the correct position, namely on the first symbol:

$\qquad \#aQ_0 \to \#a \qquad$ for all $a \in \Sigma$.

Translating the actual state transitions is straight-forward:

$\qquad \begin{align} aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\ aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\ abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q') \end{align}$

There are some technical kinks to iron out; for instance, you have to get rid of the boundary markers $\#$ at the end. That can be done by spawning two special nonterminals instead of terminating, swapping those to the ends and then removing the $\#$ along with them. Furthermore, more $\#$ have to be created on demand; that requires some hacking of the rules with $d=\#$.

Also, the construction becomes a bit more complicated if the TM uses non-input symbols. In that case, the termination rules may be wrong: if there are non-input symbols somewhere on the tape, we have not generated a proper word. This can be fixed similarly to removing $\#$: spawn a special non-terminal from $Q_0$ that is swapped to the right and only removed if all symbols are from $\Sigma$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.