0
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.