¿Cuál de los siguientes problemas es indecidible?
(A) Decidir si una gramática libre de contexto dada es ambigua.
(B) Decidir si una string dada es generada por una gramática libre de contexto dada.
(C) Decidir si el lenguaje generado por una gramática libre de contexto dada está vacío.
(D) Decidir si el lenguaje generado por una gramática libre de contexto dada es finito.
Respuesta: (A)
Explicación: la gramática independiente del contexto no se cierra bajo la ambigüedad . Un conjunto se cierra bajo una operación significa que cuando operamos un elemento de ese conjunto con ese operador obtenemos un elemento de ese conjunto.
Aquí, la gramática libre de contexto genera un lenguaje libre de contexto y el conjunto de todos los lenguajes libres de contexto también es un conjunto. Pero la ambigüedad no es una operación y, por lo tanto, nunca podemos decir que CFG está cerrado bajo la ambigüedad.
Por lo tanto, el problema mencionado en la opción (A) es indecidible.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Cuestionario 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