How to remove null production from context free grammar?

Question

How to remove null production and simply the grammar?

$$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$

Can the simplification result in this CFG?

$$ S \to a \mid aBa \\ A \to b \\ B \to b $$

Answer 1

The given grammar is: $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$

Now the algorithm for the removal of null productions is as follows:

1. We need to find all the nullable symbols from the grammar. A nullable symbol is one that generates the null string in one or more steps.

   Since $A \rightarrow \epsilon$ so the symbol $A$ is nullable.

   Due to $B\rightarrow A$ we shall have $B\Rightarrow ^* \epsilon$. So $B$ as well is nullable.

   These are the only two nullable symbols in the grammar.

2. Remove all null productions in the grammar, and use substitution for the nullable symbols to incorporate the effect which could have been obtained due to their nullable nature as follows:

   For each nullable symbol on the RHS of a production, rewrite the production, by once including it, and another time by not including it. Only with the exception that if due to this rewriting of rules, a null production is introduced, then just ignore that production.

   So for the given grammar, we have:

   For $S$ productions:

   $S \to a \mid Ab \mid b \mid aBa\mid aa$

   For the $A$ productions we have:

   $A\to b$

   For the $B$ productions we have:

   $B\to b$

Since $A$ and $B$ are unit productions, they can be removed by substituting their RHS in the productions for $S$.

So the final grammar:

$S \to a \mid bb \mid b \mid aba\mid aa$

Answer 2

Your simplification is wrong. The language of the first grammar includes $b$, but the one of the second grammar does not.

If you replace the definition of $A$ in the productions of $B$ you obtain $B \to b \mid \epsilon$. Then if you replace $A$ and $B$ with their definition in $S$ you have.

$$ S \to a \mid bb \mid b \mid aba \mid aa $$

Answer 3

To remove A->eps, you go through all right hand sides, and add right hand sides with any combinations of A’s removed. You have a rule S->Ab, so you add S->b. And you have B->A, so you add B->eps, and that all done you remove A->eps.

Now you got a new null production B->eps, so you remove that in the same way. There’s only the rule S->aBa, so you add S->aa and remove B->eps.

S->eps cannot be removed, you need that to have an empty string in the language.