Problem Solving in Automata, Languages, and Complexity

4.5 Unrestricted Grammars 195

of C’s Note that, using our grammar G, we are not able to change any B
to b before moving it to the left of all C’s. Thus, the grammar G does not
generate any string not of the form unbncn. cl

Example 4.16 Find a grammar G such that L(G) = {a2” 1 n > - 0).

Solution. The grammar G has V = {S, L, Lh, R, [ , ] } and rules

s -+ [Ral I a,

Ra -+ aaR,

aL + La,

dh __) Lha,

R] + L] 1 Lh,

[L + [R,

[Lh +&.

The main idea of the grammar G is to use a loop to generate a sentential
form [ Ra2k+’ ] from [Ra 2k 1. To do this, it first applies the second rule Ra +
aaR to move the symbol R to the right and change, along the way, each a to
au. When R reaches the right end mark 1, it changes to symbol L and moves
back to the left end to get [La2*+I] and then [&I~~+‘]. To get out of the loop,
the symbol R may change to Lh instead of L when it meets the right end
mark 1. Then, the symbol Lh moves left to cancel off with the left end mark
[. For instance, G generates aaaa as follows:

We note that, during an iteration of the loop, the nonterminal symbol R
cannot move left until it meets 1, and the nonterminal symbol L cannot change
to R until it meets [. Therefore, each iteration of the loop has to double the
number of a’s. This shows that G cannot generate strings ak if k is not a
power of 2.^0

Example 4.17 Find a grammar G such that L(G) = {ww 1 w E {u,b}*}.

Solution. The grammar G has V = {S, T, A, B, R, L,, Lb, [ ,] } and rules

S--,Tl,

RA -+ AR,

AR] + La],

AL, + L,A,

BL, + L,B,

[I,, +a[R,

[RI + &.

T+aTAIbTBI[R,

RB + BR,

RR] * Lb],

A& + Lb&

BLb + Lb&

[Lb * b[R,

This grammar uses the same idea of moving a symbol R, L, or Lb around
to change the sentential forms. First, it uses the first two rules to get S 3