¿Cuál de los siguientes problemas es indecidible?
(A) Para determinar si dos autómatas finitos son equivalentes
(B) Problema de membresía para gramática libre de contexto
(C) Problema de finitud para autómatas finitos
(D) Problema de ambigüedad para gramática libre de contexto
Respuesta: (D)
Explicación: Consulte: Problema de ambigüedad de indecidibilidad
para la gramática independiente del contexto es indecidible.
Entonces, la opción (D) es correcta.
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