A single production is a production whose body is a single nonterminal, i.e., a production of the form A -> A.  a) Give an algorithm to convert any grammar into an e-free grammar, with no single...

A single production is a production whose body is a single nonterminal, i.e., a production of the form A -> A.

a) Give an algorithm to convert any grammar into an e-free grammar, with no single productions, that generates the same language (with the possible exception of the empty string) Hint: First eliminate e-productions, and then find for which pairs of nonterminals A and B does A =4» B by a sequence of single productions.

b) Apply your algorithm to the grammar (4.1) in Section 4.1.2.

c) 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 ^ A for some nonterminal A).