182 views
0 votes
0 votes

A grammar is $\epsilon$-free if no production body is $\epsilon$ (called an $\epsilon$-production).

  1. 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$).
  2. 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. 

Please log in or register to answer this question.

Related questions