¿Cuál de las siguientes afirmaciones es falsa?
(A) El problema de la detención de las máquinas de Turing es indecidible
(B) Determinar si una gramática libre de contexto es ambigua es indecidible
(C) Dadas dos gramáticas libres de contexto arbitrarias G1 y G2 es indecidible si L(G1)=L(G2 )
(D) Dadas dos gramáticas regulares G1 y G2 es indecidible si L(G1)=L(G2)
Respuesta: (D)
Explicación: El problema de detención de la máquina de Turing es indecidible porque no existe un algoritmo para ello.
Determinar que un lenguaje libre de contexto es ambiguo es indecidible porque no existe un algoritmo para decidir que CFG es ambiguo.
El problema de equivalencia de CFG es indecidible.
Todo sobre el lenguaje regular es decidible.
La opción (D) es correcta.
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