and
A aaA aaabbc
G
⇒
⇒
(with )
$
since G and $
G are equivalent.
Ì Exam ple 2.4.2: Given a CFG as
G
S A B C E a b c P S
= ({ , , , , }, { , , }, , )
with production P given by
S
AB
A a
B
b
B C
E
c
→
→
→
→
→ / λ
Obtain L(G) and obtain an equivalent grammar L( $
G) by eliminating
useless terminals and productions.
Solu tion
L(G) is obtained as follows:
S
AB
aB
ab
⇒
⇒
⇒ .
Therefore, L(G) = {ab}.
Here
$ ({ , , }, { , }, , )
G
S A B a b P S
=
′ .
where P′ has the production rules
S
AB
A a
B
b
→
→
→
We have eliminated C as it does not derive terminal string. E and C do not
appear in any sentential form.
E → λ is a null production and hence eliminated. B C
→ simply replaces
B by C.
Ì Exam ple 2.4.3: Given G = (V, T, S, P) with P given by
S
aS A C
A a
B
aa
C
aCb
→
→
→
→
| |
Eliminate the useless symbols and productions from G.
136
Theory of Automata, Formal Languages and Computation