Chapter 4: Forma! Languages J;1 117
-------------------'------~~
In the derivation of a"b"e", we converted all B's into b's and only then
converted Cs into e·s. We show that this is the only way of arriving at a
tenninal string.
a"(BC)il is a string of terminals followed by a string of variables. The
productions we can apply to a"(BC)" are either CB .~ BC or one of aB -'> abo
bB -'> bb. bC -'> be, eC -'> ee. By the application of anyone of these
productions. the we get a sentential form which is a string of terminals followed
by a string of variables. Suppose a C is converted before converting all B's.
Then we have a"(BC)" ~ (/'bicex. where i < 11 and rx is a string of B's and Cs
containing at least one B. In ailbierx, the variables appear only in ex. As c appears
just before rx, the only production we can apply is eC -'> ee. If rx starts with
B, we cannot proceed. Otherwise we apply eC -'> ee repeatedly until we obtain
the string of the form d'biejBrx'. But the only productions involving Bare
aB -'> ab and bB -'> bb. As B is preceded by c in a"biciBrx'. we cannot convert
B, and so we cannot get a terminal string. So L(G) <;;;; {d'lJ"e/1 11 ~ I}. Thus,
we have proved that
L( G) = {a" b"eli [ 11 ~ I}
EXAMPLE 4.12
Construct a grammar G generating {xx I x E {a. b} *}.
Solution
We construct G as follows:
G = U5, 51. 5~. 53' A. B}, {a. b}, P, 5)
where P consists of
PI
5 -'> 515~53
P~, P 3 : 5.5, -'> a5 1 A.
1
_
p~, P s : A5 3 -'> S~aS3'
Pfj.. p, Ps· P 9 : Aa -'> aA,
i '
PlO, P I1
as, -'> S~a,
PI~' P l3 : SIS~ -'> A.
SIS~ -'> bSIB
BS 3 -'> S~lJS3
Ab -'> hA,
Ba -'> aB,
Bb -'> bB
Remarks The following remarks give us an idea about the construction of
productions P j-P13'
1. PI is the only S-production.
2. Using SjS~ -'> aSIA, we can add tenninal a to the left of 5] and variable
A to the right. A is used to make us remember that we have added the
terminal a to the left of S1' Using AS 3 -'> 5~aS3' we add a to the right
of S~.