196 TURING MACHINES
w [ R2(IR], where $ is the string w with symbol a replaced by A and symbol 6
replaced by B. Next, it uses symbol I& or Lb to carry a terminal symbol c1 or
6, respectively, to the left and put it to the left of the left-end mark [. This
process reverses CE R to W. The following is the deriva,tion of act6auu6u:
S - ) - T] 5 uubuTAl?AA] - 3 uubu[ RABAA] 3 uubu[ABAAR]
=P uabu[ABAL,] > uubu [ L.ABA] a uu6uu [ RABA]
3 uubua [ABAR] 3 uu6uu [ABL,] 5 uu6uu [ L,AB]
a uu6uuu [ RAB] 5 uu6uuu6u [ R] a uu6uuu6u.
Again, it is easy to see that G cannot generate strings not of the form
ulul because each nonterminal has its fixed role and can only move around as
designed. 0
Using the technique of carrying terminal symbols by nonterminals L or R, a
grammar can essentially work like a DTM, with the symbols L and R playing
the role of the tape head. The following example further demonstrates this
technique.
*Example 4. 18 Find a grammar G such that L(G) = {un6Ynm 1 n,m 2
01.
Solution. Grammar G has V = {s, A, B, 6, L, Lb, R, &, Rc, [ ,] } and rules
s + [Al, A + UA 1 B, B + 6B ( L,
UL + Lu, 6L + Lb, bL + Lb,
[Lu+a[&, [Lb + bR, VI J +&,
Rbu + uRb, &,6 __) bR,, &I + Ll,
R,b + 6RC, &I + Lb]C,
6Lb + Lbb, 7;Lb + 7;Rb,
Rb + bR, R] + E.
The grammar G generates unbmcnm wit,h a double loop structure. The
inner loop uses symbols Rb, R, and Lb to copy 6” to cm, and the outer loop
uses L to move each a to the left of the marker r to control the number of
times the inner loop is executed. One iteration of the outer loop is as follows:
.k [Lun-kbm] Ckm 3 .k+l [&un-k-lp]Ckm $ Jc+l [,n-k-l&$m] ckm* uk+l [a n-k-lj&bm-1] Clcrn > uk+l [un-k-l&m-lRc] Ckm
a .k+l [ un-k-l&bm-lLb] Ckm+l > ak+l [ un-k-ljjLbbm-l ] Ckm+l
) &+l [ un-k-lj&bbm-l ] Ckm+l > uk+l [ un-k-lrRb] C(k+l)m
3 Jc+l [ un-k-lrL] ,(k+l)m 3 ak+l [ Lp-k-lp] C(k+l)me