Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2008
Hard
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.- I, II, III and IV
- BII, III and IV only
- CI, III and IV only
- DI, II and IV only
Explanation
I is a standard CFG transformation result. II is the standard ε-production elimination procedure taught for CNF conversion. III describes exactly a right-linear (regular) grammar, which by definition generates a regular language. IV: CNF productions are X→YZ (exactly 2 non-terminal children) or X→a (a leaf) — so every derivation tree is necessarily a full binary tree. All four are true.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.