Solu tion
Here V = {S, A, B, C}. Let us determine the set of variables that can lead to a
terminal string.
Since A a
→ and B
aa
→ , implies A and B belong to this set. Also S
belongs to this set, since S
A a
⇒ ⇒ .
But C does not belong to this set because C does not produce terminals
since C
aCb
→
.
Thus C is removed and its corresponding productions are also removed.
S
aS A
A a
B
aa
→
→
→
|
Here V 1 = {S, A, B}.
To eliminate the variables that cannot be reached from the start variable, a
“dependency graph” is drawn and decided.
The dependency graph for V 1 = {S, A, B} is drawn as below.
A variable is useful only if there is a path from the vertex labeled S to the
vertex labeled with that variable.
From the above fig. it is obvious B is useless. Hence we have
$ ( $ , $ , , $ )
G V T S P
=
with $ { , }
V
S A
=
, $ { }
T
a
=
and P given by
S
aS A
A a
→
→
|
.
Ì Exam ple 2.4.4: Given a CFG with P given by
S
aS b
S
aS b
→
→
1
1
1 | λ
obtain a new set of P for a gram mar same as the given CFG.
Solu tion
The given grammar
S
aS b
S
aS b
→
→
1
1
1 | λ
gen er ates the λ-free lan guage given by
Con text-free Grammars
137
S
B
A