-
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 ε-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 → W or X → WY (where, W is a string of terminals and Y is non terminal), is always regular.
4. The derivation trees of strings generated by a context free grammar in Chomsky Normal Form are always binary trees.
-
- 1, 2, 3 and 4
- 2, 3 and 4
- 1, 3 and 4
- 1, 2 and 4
- 1, 2, 3 and 4
Correct Option: C
Statement 1 is true : Using GNF we can convert Left recursive grammar to right recursive and by using reversal of CFG and GNF we can convert right recursive to left recursive.
Statement 2 is false : because if Î is in the language then we can't remove ∈ production from Start symbol. (For example L = a*)
Statement 3 is true because right linear grammar generates regular set
Statement 4 is true, only two non-terminals are there in each production in CNF. So it always form a binary tree.
