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.