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 $$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityHow 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 $$
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 $$
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.