Problem Solving in Automata, Languages, and Complexity

100 CONTEXT-FREE LANGUAGES

q-4-J = -2. It follows that for some i,^1 < - i < - n - 1, d(wi) = -1. So,
W = wiv and both wi and v are in A.
By the above claim, A = aS U bAA. Similarly, we get B = bS U a B B.
From the above analysis, we obtain the following context-free grammar
G= ({~,4B),{a,b~,R,S), w h ere R consists of the following rules:

S --+ E 1 aB 1 bA, A -+ aS 1 bAA, B --+ bS 1 aBB. •I

Example 3.12 Find a context-free grammar that generates the language

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

Solution. Let f(x) = 2#,(x) - #b(x). Then L = {x E {a, b}* 1 f(x) = 0).
The values of f on the prefix sequence of any string change in the following
ways:

(a) Each increasing is in value 2;
(b) Each decreasing is in value 1.
We define four nonterminal symbols S, A, B and C to represent four lan-
guages over {a, b} as follows:

(i) S represents L = {x 1 f(x) = 0);

(ii) A = {x I f(x) = 1);

(iii) B = {x I f(z) = -1);

(iv) C = {x I f(x) = 2).

Then, it is easy to see that S = E: U aB’ U bA, where B’ = {x I f(x) = -2).
Now, every string w E B’ of length n has f(2U0) = 0 and f(wn) = -2, where
wi denotes the prefix of w of length i. By property (b) of the function f, we
know that there must be a prefix wj of w with f(wj) = -1. Thus, we know
that B’ = BB. Or, equivalently, S = E U aBB U bA.
Next, it is easy to see that A = bC U a B. Also, from the above analysis,
we know that B = bS U aBBB.
Finally, we note that C can be expressed as aS U bAC U bCA. To see this,
we let C’ = {x 1 f(x) = 3). Th en, for any string x E C’ with length n, we
have f(x0) = 0 and f(xn) = 3, where xi denotes the prefix of x of length
i. Then, by property (a) of f, there must be a prefix xj of x with either
f(xj) = 1 or f(xj) = 2. In th e fi rs t case, xj E A and y E C; and in the second
case, xj E C and y E A, where y is the suffix of x such that x = xjy.
Now, from the above analysis, we obtain the following context-free gram-
mar: G=({S,A,B,C},{a,b},R,S) w h ere R consists of the following rules:

S -+ E I aBB I bA, A --+ aB I bC,

B ---+ bS I aBBB, C -+ aS I bAC I bCA. 0