4.5 Unrestricted Grammars 197
5’ 3 [A] 3 [uaA] a [auB] % [aubbbB] 3 [uabbbL]
% [ Luubbb] a a [ Rbubbb] a a [ uRbbbb] 3 a [ ubR,bb]
% u[abbbR,] a u[ubbbLb]c 3 u[ubLbbb]c 3 u[u&Rbbb]c
3 u[abbR,b]c) u[ubbbR,]c 3 u[ubbbL&z
3 u[ubbbR,] --- cc 3 a[abbbLb]ccc --- 3mm-
u[ubbbRb]ccc
---
+ u[ubbbL] ccc 3 a [ Lubbb] ccc 3 au [ Rbbbb] ccc% uu[bbbRb] --- c6 3 uu[bbbL]c6 --- 3 uu[Lbbb]$
* uubRbb] c6 % uubbbR] c6 3 u2b3c6. clWe now generalize the idea of the above examples to show that a grammar
can simulute a DTM.
Theorem 4.19 For any one-tupe DTM M = (Q, C, I’,& s), there exists a
grammar GM = (V, C, R, S), with V = Q U (I? - C) U { [ ,] }, such that for any
configurations (q, xcty) and (p, x/by’), wherep, q E Q, u, b E r, and x, y, x’, y’ E
r*,
(q, XUJ) k; (p, x%y’) if and only if [ xquy] 2 [x’pby’ 1.Proof. The idea is to use a word [ xquy] E (VUc>* to represent a configuration
(q, xay) of the machine A&, and to use the rules of the grammar GM to simulate
the instructions of TM AL More precisely, we define GM as follows:
(1) For each instruction s(Q, a) = (p, b, L), where b # B, GM has the rules
cqu + pcb, for all c E r.
(2) For each instruction s(Q, a) = (p, B, L), GM has the rules
cqud + pcBd, for all C, d E I’,
and the rules
cqal + P4 for all c E r.
(3) For each instruction 5(q, a) = (p, b, R), GM has the rules
quc + bpc, for all c E r,
and the rule
It is clear that using these rules, we get [ xquy] a [ x’pby’] if and only
if (4, GY) k (P, X’bY’)* It follows that [ xquy ]^5 [ x’pby’ ] if and only if
(a, %Y) F (P, x’by’). cl