3.2 ExampIes of Context-Free Grammars 99
- A context-free grammar G = (V, C, R, S) is said to be linear if every
rule of it is of the form A -+ zB or A + Bz or A -+ cc, where A, B E V
and x E C*. Show that a language generated by a linear grammar is
not necessarily regular. - For each of the following languages L, construct a context-free grammar
that generates L:
(a) {unbm 1 772 > 72,772 - n is even}.
(b) (2~~ 1 x E 6, b}*, #&c) = nor #b(x) = n}, where #&c) denotes
the number of occurrences of symbol a in string x.
(4 {xcn I x E -w)‘, #a(x) + #b(X) > - n}.3.2 More Examples of Context-Free Grammars
In this section, we study more techniques of constructing context-free gram-
mars. Our first new idea is that in a context-free grammar G = (V, C, R, S),
each nonterminal symbol A E V represents a language, that is, the set of
strings x E C* with a derivation A 2 x. Therefore, when we design a
context-free grammar, we may designate a few nonterminal symbols to rep-
resent some specific languages and use the grammar rules to express their
relations.
Example 3.6 (Revisited) Find a context-free grammar that qenerates.
L = {x E {a, b}* 1 x has as many u’s as b’s}.
Solution 2. Let us use the notation #a(z) to denote the number of occurrences
of symbol a in a string x. For convenience, we will use a capital letter S, A
or B to denote both a nonterminal symbol of the grammar and the set of
strings for which there is a derivation from that symbol. We let the symbol
S represent the language L, the symbol A represent the set of strings x with
#u(x) = ,#b(x) + 1, and the symbol B represent the set of strings x with
#u(x) = #b(x) - 1.
Now, let x be a string in S. Then, either x = E or x = uy for some
y E {a, b}* or x = bx for some x E {u,b}*. If x = uy then Sjta(y) = #b(y) - 1,
andsoyEB. Ifx = bx then #&z) = #b(z) + 1 and, so x E A. Therefore, we
get the relation S = E U uB U bA. This relation can be expressed in grammar
rules as S + E I uB I bA.
Next, we study strings represented by A and B. First, if a string x is in A,
then either x E US or x E bA’, where A’ represents the set of strings x with
#a(z) = #b(Z) + 2.
We claim that strings in A’ can always be decomposed into the concate-
nation of two substrings in A. To see this, we use the same argument as in
Solution 1: Let d(w) d enote #b(w) - #&u) and wi denote the prefix of w
of length i. Then, for a string w of length n, w E A’ implies d(wg) = 0 and