Problem Solving in Automata, Languages, and Complexity

3.1 Context-Free Grammars 93

Solution. Using the matching approach, we need to match, in a string x E L,

each b with an a which occurs to its left (allowing some a not matched with

any b). Since the order of the occurrences of a and b is only partially fixed,

this matching idea appears hard to work out. Instead, we use the recursive

method to construct the required grammar.

How can we express longer strings in L by shorter strings in L? First, if

x= E, then we know that x E L. For nonempty string x E L, we note that

the first symbol of x must be a since the first symbol itself is a prefix of x.

Therefore, we can write x = ay. Now, if y E L, then x = ay is the recursive

expression we are looking for.

Next, let us consider the case when y is not in L. In this case, y must have

a prefix which contains one more b than a. Let u be the shortest such prefix of

y. Then, the last symbol of u must be b. Let us write u = wb and x = awbx.

Now, we argue that w and x must be in L. First, by the definition of u, each

prefix of w has at least as many a’s as b’s. That shows w E L. Furthermore,

u= wb has exactly one more b than a. So, awb has as many u’s as b’s. Now,

assume that t is a prefix of Z. Then, awbt is a prefix of x and, so, has at least

as many ells as b’s. It follows that t has at least as many a’s as b’s, This shows

that x is in L.

The above analysis shows that a nonempty string x E L can be expressed

as either x = ay for some y E L or x = awbx for some w,x E L. Using

S as the starting symbol to generate all strings in L, we see that L can be

generated by the grammar G = ({S}, {a, b}, R, S) with the following rules:

S -+ E 1 aS 1 aSbS.

For instance, the string aababbab is generated as follows:

S 3 aSbS > aaSbSbS + aabSbS * aabaSbSbS

5 aababbS + aababbaSbS > aababbab.

Example 3.6 Find a context-free grammar that generates

L = {x E {a, b}* 1 x has as many a’s as b ‘s}.

Solution. Let us analyze how a string x in L looks like. First, for any string
w in {a,b}, let d(w) be th e number of b’s in w minus the number of a’s in
w. Thus, L = {x E {a, b} 1 d(x) = 0). N ow, suppose that u is the shortest
nonempty prefix of x having d(u) = 0. Assume that u starts with symbol b.
Then, we claim that u must end with symbol a.
Proof of Claim. Let us assume that (ul = k and, for 1 < - i < - k, let ui be
the prefix of u of length exactly i. Consider the sequence (~1, ~2,... , uk) of
the prefixes of u. In this sequence, since the lengths lual increase from one
string to the next string by exactly one, the values of d(u& from one to the
next, also differ by exactly one. Now, we note that if u ends with symbol b,