Problem Solving in Automata, Languages, and Complexity

3.2 Examples of Context-Free Grammars 101

Example 3.13 Find a context-free grammar for the language

L = {x: E {a,b}* 1 #b(X) = 2#,(x) + 3).

Solution. From the analysis of Example 3.12, we know that every string z in

L can be decomposed to be II: = yx with y E A, x E C, or with y E C, x E A.

So, we obtain a grammar Gr = ({&,S,A, KC}, {O}, RI, SI) for L, where

RI contains all rules in G of Example 3.12, plus the rules

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

L = {ambncpdq 1 m + n = p + q}.

Solution. The equation m+n = p+q suggests that we use the idea of matching
to find the correct rules. That is, we need to match letters a and b with letters
c and d, and we should do it in a recursive way. Since we do not know the
exact relations between the sizes m, n, p, 4, we will perform these matchings
in stages. At each stage, we match the two outermost symbols and continue
until we run out of one type of symbols.
(1) In stage S, we use the rule S --+ aSd to genearate a number of a’s with
the same number of d’s. Then, depending on whether m > - q, we move
to stage A or stage B by the rules S -+ A 1 B.
(2) In stage A, we deal with the case m > q. We generate some a’s with
the same number of c’s, and then mo& to stage C. That is, we create
rules A + aAc 1 C.
(3) In stage B, we deal with the case m < q. We generate some b’s with
the same number of d’s, and then move to stage C. That is, we have
the rules B + bBd ( C.
(4) Finally, in stage C, we match symbols b with symbols c with the rules
C + bCc I E.
The complete set of grammar rules are as follows:

S + aSd I A 1 B, A + aAc 1 C,

B + bBd I C, C + bCc I E.

Note that if a string z = a”bncPdQ in L has m > q, then the derivation
of x starts. from stage S then moves to stage A and then to stage C, while
a string y with m < q must go through stages S, B and C. A string x with
m = q can be derived in either way. Cl

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

L = {amb”cp I m + 2n > - p}.