Which of the following statements are true? I. Every left-recursive grammar…
2008
Which of the following statements are true?
I. Every left-recursive grammar can be converted to a
right-recursive grammar and vice-versa
II. All ϵ productions can be removed from any context-free
grammar by suitable transformations
III. 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 a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar
in Chomsky Normal Form are always binary trees - A.
I, II, III and IV
- B.
II, III and IV only
- C.
I, III and IV only
- D.
I, II and IV only
Attempted by 14 students.
Show answer & explanation
Correct answer: C
Statement I is true because left-recursive and right-recursive grammars are equivalent in expressive power and can be converted into each other. Statement II is false because not all CFGs allow removal of ε-productions without altering the language, especially if ε is in the language. Statement III is true because such productions generate regular languages (right-linear grammars). Statement IV is true as Chomsky Normal Form ensures binary derivation trees. Thus, I, III, and IV are correct.
A video solution is available for this question — log in and enroll to watch it.