DHARM
NON-REGULAR GRAMMARS 299
Lemma 11.1
Let G = (VN, VT, S, P) be a CFG that allows null production/s (A → ∈) then the language L(G)
- {∈} can be generated from a equivalent grammar G′ = (VN′, VT′, S′, P′) such that G′ has no
null production.
So, Grammar G′ has a new production
Snew → S | ∈ followed by all productions derive from S as usual.
Constructive proof
Assume a grammar G has the productions
S → a b | AB | A
A → B | a
B → S | b | ∈
Then remove all null productions from G.
Observe the null production/s of the grammar G. Remove all null productions such that
resultant grammar generates the similar language excluding string ∈.
l We find the production B → ∈ is a null production (nullable B) so remove it from G.
(–) B → ∈
(+) S → A
(+) A → ∈
So, add two new productions in the grammar because, all the productions that derive
including symbol B are manipulated according to following possibilities:
If we use the definition B → ε then S → A B becomes S → A and A → B becomes A → ∈.
Otherwise, production S → A B and A → B remains in the grammar for using next
production definitions B → S and B → b.
The, new set of productions are
S → a b | A B | A | A remove duplicate productions i.e.
So, Grammar becomes
S → a b | A B | A
A → B | a | ∈
B → S | b
l Next null production is A → ∈ (A is nullable), remove it from the grammar i.e.,
(–) A → → ∈
(+) S → ∈ (S → ∈ can be derive from S → A when A → ∈)
(+) S → B (S → B can be derive from S → A B when A → ∈)
Thus, new set of productions are.
S → a b | A B | A | B | ∈
A → B | a
B → S | b
