A grammar is $\epsilon$-free if no production body is $\epsilon$ (called an $\epsilon$-production).
- Give an algorithm to convert any grammar into an $\epsilon$-free grammar that generates the same language (with the possible exception of the empty string - no $\epsilon$-free grammar can generate $\epsilon$).
- Apply your algorithm to the grammar $S\rightarrow aSbS\mid bSaS\mid \epsilon$. Hint: First find all the nonterminals that are nullable, meaning that they generate $\epsilon$, perhaps by a long derivation.