¿Cuál de los siguientes es/son indecidibles?
(A) 3 solo
(B) 3 y 4 solo
(C) 1, 2 y 3 solo
(D) 2 y 3 solo
Respuesta: (D)
Explicación:
- El primero es Vacío para CFG; si un CFG está vacío o no, este problema es decidible.
- Segundo es todo para CFG; si un CFG generará todas las strings posibles (completitud de CFG), este problema es indecidible.
- El tercero es Regularidad para REC; si el lenguaje generado por TM es regular es indecidible.
- El cuarto es la equivalencia de regular; se puede decidir si el lenguaje generado por DFA y NFA es el mismo.
La segunda y la tercera serán indecidibles. Por lo tanto, 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