Eliminating Epsilon Productions

In this class, We discuss Eliminating Epsilon Productions.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of eliminating left recursion grammar. Click Here.

Example 1:

S – aSa | bSb | ε

To eliminate epsilon from the given grammar, we need to substitute epsilon and find the possibilities.

In the above grammar, we have production S – ε

We substitute epsilon in place of S.

First, We substitute epsilon in bSb. After substituting epsilon, we get bb.

This bb should be added as a new production to S.

Similarly, we substitute in aSa. We get aa.

The final productions after substituting epsilon are

S – aSa | bSb | aa | bb.

No need to write epsilon again to the nonterminal S.

Example 2:

S – Xa

X – aX | bX | ε

Substitute epsilon in place of X and write all the new productions possible.

For the production S – Xa, we get S – Xa | a

Similarly for X we get X – aX | bX |a | b

Example 3:

S – AB

A – aAA | ε

B – bBB | ε

First, we substitute epsilon in place of B. We have to write all the possibilities.

Substituting epsilon in single B and in both the B’s we get the following productions

B – bBB | bB | b

Similarly, we substitute for A and B. The final productions are

S – AB | A | B | ε

A – aAA | aA | a

B – bBB | bB | b

Important point: The production S has epsilon.

We can not eliminate epsilon from S. because the language itself accepts epsilon.

Example 4:

S – ACB | cbB | Ba

A – da | BC

B – gC | ε

C – ha | ε

as B – ε and C – ε

After substituting BC, we get A also accept epsilon.

After substituting A, B, C epsilon, we get S also accept epsilon.

The reader should understand the above points.

The below grammar shows the final CFG after eliminating epsilon.

S – ABC | A | B| C| AB | BC | AC | cb | cbB | a | Ba | ε

A – da | BC | B | C

B – gC | g

C – ha