Problem Solving in Automata, Languages, and Complexity

194 TUIUNG MACHINES

finite set of terminal symbols, with C n V = 8, S E V is the starting symbol,

and R is a finite set of production rules each of the form

for some x E (V U C)+ and y E (V U C)*.

The notion of derivations x * y and x & y is the same as that of a

G G

context-free grammar G. Namely, for x E (V U C)+ and y E (V U C)“, we

write x ~2 y if x = uww, y = uxv for some u, v E (V U C)* and some rule

w+zinR. ForxE(VUC)+andyE(VUC)*,wewritex & yif

G

there exists a sequence of strings x0, xl,... , X~ E (V U C)* such that x = x0,

Y = Xn9 and xi^2 xi+1 for i = 0, 1,... , n - 1. When the grammar G is

understood, we may write x + y and x % y for x 2 y and x 1% y,

respectively. We say a grammar G generates a string w E C* if S =$ w. We

let L(G) = {w E I=* 1 S :A 20).

G

It is obvious that every context-free language can be generated by an unre-

stricted grammar, since context-free grammars are just special cases of unre-

stricted grammars. In general, unrestricted grammars can generate languages

that are not context-free.

Example 4.15 Find a grammar G such that L(G) = {anbncn 1 n > - 0).

Solution. The grammar G has nonterminals S, B, C, and the following rules:

S + aSBC 1 E, CB --+ BC,

aB + ab, bB + bb,

bC + bc, cc ___) cc.

How does G generate anbncn? It consists of three steps. First, it applies the
first rule n times and the rule S + E once to get a string a” (BC)n. Second, it
applies the rule CB -+ BC for n(n - 1)/2 times to move all B’s to the left of
all C’s to get a string an B”C”. Finally, it uses the last four rules to change
every B to b and every C to c. The following is the derivation of string a3b3c3.
We underline the substring of a sentential form that is to be replaced in the
next step.

S - + aSBC - * aaSBCBC - 3 aaaSBCBCBC - + aaaBCBCBC

3 aaaBBCCBC + aaaBBCBCC 3 aaaBBBCCC

3 aaabBBCCC $ aaabbbCCC > aaabbbcCCC % aaabbbccc.

Why don’t we use the simpler rules B + b and C -+ c for the third step?

That is because we do not want to let the grammar skip the second step and

change all symbols B and C to b and c without first moving B’s to the left