Question

Which of the following statements are true?
1. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa.
2. All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations.
3. The language generated by a context-free grammar all of whose productions are of the form X $\to w$ or X $\to wY$ (where, w is a string of terminals and Y is a non-terminal), is always regular.
4. The derivations trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees.

• A. 2,3 and 4 only
• B. 1,2 and 4 only
• C. 1,2,3 and 4
• D. 1,3 and 4 only

Answer 1

The correct option is D 1,3 and 4 only

1. True
2. All $\epsilon$-productions can be removed from only context free grammars that produce $\lambda$-free CFL's.
If $\lambda ϵL\left(G\right),$ then all $\epsilon$-productions cannot be successfully removed. So 2 is false.
3. True
4. True, since in Chomsky normal form, every production is of the form of A $\to$ BC or A $\to$ a.
An example of a binary tree generated by CNF derivation is shown below: