PUERTA | PUERTA CS 2008 | Pregunta 50

¿Cuáles de las siguientes afirmaciones son verdaderas?

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 y IV
(B) II, III y IV solamente
(C) I, III y IV solamente
(D) I, II y IV solamente

Respuesta: (C)
Explicación:  
I es cierto como podemos siempre elimine la recursividad izquierda de cualquier gramática dada.
(Para una mejor comprensión, vea esto ).
 
II es falso ya que podemos eliminar todas las producciones de épsilon solo si la gramática no contiene épsilon en el idioma.
 
III es cierto ya que es la definición de gramática regular.
(Para una mejor comprensión, consulte los idiomas de tipo 3 en este artículo ).
 
IV es cierto porque en la forma normal de chomsky, todas las producciones son del tipo X -> YZ o X -> t, donde X, Y, Z son variables y ‘t’ es una string terminal. Cuando dibujamos el árbol de derivación para cada Node, hay como máximo 2 hijos. Es por eso que los árboles de derivación de gramáticas en forma normal de chomsky son árboles binarios.
(Para una mejor comprensión, vea esto .)
 
Por lo tanto, C es la opción correcta.
Cuestionario de esta pregunta