¿Cuál de los siguientes problemas es indecidible? [2007]
(A) Problema de membresía para CFG
(B) Problema de ambigüedad para CFG.
(C) Problema de finitud para FSA.
(D) Problema de equivalencia para FSA.
Respuesta: (B)
Explicación:
Un conjunto es cerrado bajo una operación significa que cuando operamos un elemento de ese conjunto con ese operador obtenemos un elemento de ese conjunto.
Aquí, CFG genera una CFL y el conjunto de todas las CFL es el conjunto. Pero la ambigüedad no es una operación y, por lo tanto, nunca podemos decir que CFG está cerrado bajo tal operación.
Solo el problema de ambigüedad para los CFG es indecidible.
Por lo tanto, la opción (B) es correcta.
Comente a continuación si encuentra algo incorrecto en la publicación anterior.
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