Mathematical Foundation of Computer Science

DHARM

300 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l S → ∈ is a nullable production (S is nullable), remove it from G, i.e.,
(–) S → ∈
(+) B → ∈ (B → ∈ can be derive from B → S when S → ∈)
Thus, new set of productions are,
S → a b | A B | A | B
A → B | a
B → ∈ | b
Again symbol B becomes nullable so we find a cycle of occurrence of nullable symbols
that never terminate. Hence the sequential removal of nullables might not free the grammar
from null production. Therefore, we search for alternate method of elimination of null produc-
tion/s.
Hence, we ask for another method of elimination of null production/s.
Algorithm
(For finding the nullable)
//Assume a grammar G = (VN, VT, S, P)
1 begin
2 old V = ∅; // old V is the set of nullable symbols
3 new V = {A ∈ VN | A → ∈ is in P}; // new V is the set of
nullable currently search
4 while (Old V ≠ New V) do
5 begin
6 old V = new V;
7 new V = new V ∪ {A ∈ VN | A → α is in P and α ∈ (old V)*};
8 end;
9 end.
Fig. 11.19
Example 11.18. Simplify the following grammar and find nullable symbols.
S → a b | A B | A
A → B | a
B → S | b | ∈
Sol. Since we know that symbol N is nullable if N derives ε in one/more derivations, i.e.

N ⇒N ∈

Thus G contains following {B, A, S} are the nullables.

Explanation

Using algorithm shown in Fig. 11.19, initially old V set contains no nullable (line 2). After line
3 we get symbol B is in set new V. while new V is not equal to old V repeat line 6 and 7.
l First iteration,
old V = {B} and new V = {B} ∪ {A} or {B, A} because A → B and B ∈ old V.
l Second iteration,
old V = {B, A} and new V = {B, A} ∪ {S} or {B, A, S} because S → A B and A B ∈ (old V)*.