A grammar is e-free if no production body is e (called an e-productiori). a) Give an algorithm to convert any grammar into an e-free grammar tha t generates the same language (with the possible...

A grammar is e-free if no production body is e (called an e-productiori).

a) Give an algorithm to convert any grammar into an e-free grammar tha t generates the same language (with the possible exception of the empty string — no e-free grammar can generate e).

b) Apply your algorithm to the grammar S aSbS \ bSaS | e. Hint: First find all the nonterminals tha t are nullable, meaning tha t they generate e, perhaps by a long derivation.