Theory of Computation – Eliminating null production from the productions in the Context Free Grammar

Null productions are of the form A -> ϵ. In this tutorial we will learn to remove the null productions from the grammar. We cannot remove all ϵ-productions from a grammar if the language contains ϵ as a word, but if it doesn’t we can remove all. In a given CFG, we call a non-terminal N nullable if there is a production N -> ϵ or there is a derivation that starts at N and leads to ϵ:
N => … => ϵ.

If A -> ϵ is a production to be eliminated then we look for all productions, whose right side contains A, and replace each occurrence of A in each of these productions to obtain the non ϵ-productions. These resultant non ϵ-productions must be added to the grammar to keep the language the same.

Example: Remove the null productions from the following grammar
S -> ABAC
A -> aA / ϵ
B -> bB / ϵ
C -> c
Solution:
We have two null productions in the grammar A -> ϵ and B -> ϵ. To eliminate A -> ϵ we have to change the productions containing A in the right side. Those productions are S -> ABAC and A -> aA.
So replacing each occurrence of A by ϵ, we get four new productions
S -> ABC / BAC / BC
A -> a
Add these productions to the grammar and eliminate A -> ϵ.
S -> ABAC / ABC / BAC / BC
A -> aA / a
B -> bB / ϵ
C -> c
To eliminate B -> ϵ we have to change the productions containing B on the right side. Doing that we generate these new productions:
S -> AAC / AC / C
B -> b
Add these productions to the grammar and remove the production B -> ϵ from the grammar. The new grammar after removal of ϵ – productions is:
S -> ABAC / ABC / BAC / BC / AAC / AC / C
A -> aA / a
B -> bB / b
C -> c

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.
If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.