The GATE Grind

GATE 2008 CS – Question 50

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

Which statements are true?

I. Every left-recursive grammar can be converted to right-recursive and vice versa.

II. All ε-productions can be removed from any CFG by suitable transformations.

III. A CFG with rules X→w or X→wY, w terminal string, is always regular.

IV. Derivation trees of strings generated by a Chomsky-normal-form CFG are always binary trees.

  1. I, II, III and IV
  2. II, III and IV only
  3. I, III and IV only
  4. I, II and IV only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) I, III and IV only

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →