¿Cuál de las siguientes afirmaciones es falsa?
(A) Existen lenguajes libres de contexto tales que todas las gramáticas libres de contexto que los generan son ambiguas
(B) Una gramática libre de contexto no ambigua siempre tiene un árbol de análisis único para cada string del lenguaje generado por ella.
(C) Tanto los autómatas pushdown deterministas como los no deterministas siempre aceptan el mismo conjunto de lenguajes
(D) Un conjunto finito de strings de un alfabeto es siempre un lenguaje regular.
Respuesta: (C)
Explicación:
A) Para los lenguajes de programación del mundo real, la referencia CFG suele ser ambigua, debido a problemas como el problema de los demás. // Wikipedia
B) Una string es ambigua si tiene dos árboles de análisis distintos; la gramática no es ambigua si una string tiene árboles de análisis distintos.
C) Los autómatas pushdown deterministas pueden reconocer todos los lenguajes libres de contexto deterministas, mientras que los no deterministas pueden reconocer todos los lenguajes libres de contexto.
Por lo tanto es FALSO
D)Propiedades del Lenguaje Regular:
- El conjunto de lenguajes regulares sobre un alfabeto
se cierra bajo las operaciones unión, concatenación y estrella Kleene. - Los lenguajes finitos son regulares.
Así que la respuesta es C
Quiz de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA