A single production is a production whose body is a single nonterminal, i.e., a production of the form $A\rightarrow A$.
- Give an algorithm to convert any grammar into an $\epsilon$-free grammar, with no single productions, that generates the same language (with the possible exception of the empty string) Hint: First eliminate $\epsilon$-productions, and then find for which pairs of nonterminals $A$ and $B$ does $A\overset{\ast}{\Rightarrow}B$ by a sequence of single productions.
- Apply your algorithm to the grammar
$$E\rightarrow E+T\mid T$$
$$T\rightarrow T\ast F\mid F$$
$$F\rightarrow (E)\mid id$$
- Show that, as a consequence of part $(a)$, we can convert a grammar into an equivalent grammar that has no cycles (derivations of one or more steps in which $A\overset{\ast}{\Rightarrow}A$ for some nonterminal $A$).
