Problem Solving in Automata, Languages, and Complexity

92 CONTEXT-FREE LANGUAGES

Now, if we replace each A by either a or bb, we get a sentence of the form

(a + bb)(ba + bbb)n(a + bb)“+’

Thus, L(G2) consists of all these strings with n > - 0. cl

There are many techniques for designing a context-free grammar to gener-

ate a given language. We first introduce two basic concepts: matching and

recursive relation. More ideas will be studied in the next section.

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

L = {On12” 1 n > - 0).

Solution. This language is like L(G1) of E xample 3.1, in the sense that if we

replace each 1 of Gr by 11 then we get a grammar for L. So, the required

grammar is G = (-K% -P, 11, (s + E I os111, S). q

Starting from scratch, we may construct the above grammar in two ways.

First, we observe that the rule S + OS11 always generates a matching pair

of 0 and 11. Applying this rule n times, we get a sentential form OnS( 11)“.

This simple type of rules and their variations are very useful in the design of

context-free grammars.

Another way to find the grammar is to try to get a recursive expression

of the longer strings in L in terms of the shorter strings in L. Namely, a

longer string 0 n+112(n+1) in L can be written as O(OY2”)ll. Thus, if there is

a derivation S 5 0” 12n, then we need a rule S + OS11 to get a derivation

S $ O”+112(n+1). W f ur th er d e emonstrate this idea in the next few examples.

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

L = {x E {o,1}* 1 Lc = P}.

Solution. We may view this problem as a matching problem: the leth leftmost
symbol of input II: must be equal to the kth rightmost symbol of x. We can
use the rules S ---+ OS0 and S + 1Sl to enforce this matching relation.
We can also view this problem as a recursive relation problem: a string
IX: E L of length 2n + 2 can be written as either OyO or lyl for some y E L
of length 2n. Thus, we need rules S -+ OS0 and S --+ 1Sl to generate x
recursively.
From the above ideas, it is easy to see that L can be generated by a grammar
G = ({S), (0, 11, R, S), w h ere R contains the following rules:
s __) E lo I1 I OS0 I 1Sl. cl

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

L = {x E {a, b}’ I each prefix of x has at least as many a’s as b’s}.