Which of the following statements are true? I. Every left-recursive grammar…

GATE · 2008 · CS

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 

  1. A.

    I, II, III and IV

  2. B.

    II, III and IV only

  3. C.

    I, III and IV only

  4. D.

    I, II and IV only

Attempted by 57 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…