116 ~ Theory of Computer Science
EXAMPLE 4.11
Construct a grammar G generating {a"b"e ll i n ~ l}.
Solution
Let L = {a"b"e"l n ~ I}. We try to construct L by recursion. We already know
how to construct a"Y' recursively.
As it is difficult to construct allb"e" recursively, we do it in two stages:
(i) we construct alld' and (ii) we convert d' into bne". For stage (i), we can have
the following productions S ~ aSa Iaa. A natural choice for a (to execute
stage (ii)) is be. But converting (be)" into bile" is not possible as (be)" has no
variables. So we can take a = BC, where Band C are variables. To bring
B's together we introduce CB ~ BC. We introduce some more productions
to convert 8's into b's and Cs into e·s. So we define G as
G = ({ S, B, C}, {a, b, e}, P. S)
where P consists of
S ~ aSBC I aBC, CB ~ BC, aB ~ ab, bB ~ bb, bC ~ be, eC ~ ee
S =? aBC =? abC =? abc
Thus,
abc E UG)
Also,
S ~ o"-1S(BO,,-1
=? a"-laBC(BO,,-1
=? all-IabBII-IC"
=> a"b"C"
=? allb"-lbeC"-l
=? a"b"e"
Therefore.
by applying S ~ aSBe
by applying S ~ aBC
by applying CB ~ Be
(since CB ~ BC
interchanges Band 0
by applying aB ~ ab
by applying bB ~ bb
by applying bC ~ be
by applying eC ~ cc
(n - 1) times
several times
once
several times
once
several times
L(G) <;;;; {a"b"c" In ~ I}
To show that {d'b"c"ln ~ I} <;;;; L(G), it is enough to prove that the only
way to arrive at a terminal string is to proceed as above in deriving a"b"e"
(n ~ 1).
To start with, \ve have to apply only S-production. If we apply S ~ aBC.
first we get abc. Otherwise we have to apply S ~ aSBC once or several times
and get the sentential form a"-1 S(BCjJ1-1. At this stage the only production we
can apply is S ~ aBC, and the resulting string is o"(BO II .