114 9 Theory of Computer SCience
If x is a palindrome of odd length, then x = ala:
anca" ... al' where
ai's and c are either a or b. So S :::S al ... anSa n
al =::} x by applying
S --'7 aSa, S --'7 bSb and finally, S --'7 a or S --'7 b. Thus. x E L(G). This proves
L = L(G}.
EXAMPLE 4.7
Construct a grammar generating L = {wnv
T
Iw EO {a, b} *}.
Solution
Let G = ({S}, {a, b. c}, P, S), where P is defined as S --'7 aSa I bSb I c. It
is easy to see the idea behind the construction. Any string in L is generated
by recursion as follo\\'s: (i) eEL: (ii) if x E L. then wxw
T EO L. So, as in
the earlier example. we have the productions S --'7 aSa I bSlJ i c.
EXAMPLE 4.8
Find a grammar generating L = {d'lJ"c
i I II 2: L i 2: O}.
Solution
L = L 1 u L:
L 1 = {al/b"l II 2: I}
L, = {a" b"c
i i II 2: L i 2: I}
We construct L 1 by recursion and L: by concatenating the elements of L 1
and c
i • i 2: 1. We define P as the set of the following productions:
S--'7A,
A --'7 ab,
A --'7 aAb,
S --'7 Sc
Let G = ({S. A}, {a. b, c}, P. S). For n 2: L i --'7 0, we have
Thus.
{a"b"c' In 2: L i 2: O} ;;;::; L(G)
To prove the reverse inclusion. we note that the only S-productions
are S --'7 Sc and S --'7 A. If we start with S --'7 A, we have to apply
A =::} d
,
- I Ab,,-l :::S a
l1 b". and so d
1
b"co EO LCG)
If we start \vith S --'7 Sc, we have to apply S --'7 Sc repeatedly to get SCi. But
to get a tenninal string. \ye have to apply S --'7 A. As A :::S a"lJ", the resulting
terminal string is a"b"c
i . Thus, we have shown that
L(G) ;;;::; {a" b"c
i
III 2: L i 2: O}
Therefore.
L(G) = {all b"c
i
In 2: L i 2: O}