Ullman--Chomsky Normal Form

Question

If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it.

S->ASB|epsilon

A->aAS|a

B->SbS|A|bb

Comments

if epsilon in your grammar you cannot romove all epsilon production

---

In case of Start symbol we have to keep it. Can't remove epsilon production of start symbol.

Answer 1

1. S->ASB/AB/epsilon
2. A->aAS/aA/a
3. B->SBS/SB/BS/B/A/bb
4. after removing epsilon production

Comments

thanks!