Considere los siguientes problemas:
- (i) ¿Si un autómata finito se detiene en todas las entradas?
- (ii) ¿Es regular un determinado lenguaje libre de contexto?
- (iii) ¿Calcula una máquina de Turing el producto de dos números?
¿Cuál de las siguientes es correcta?
(A) Solo (ii) y (iii) son problemas indecidibles
(B) (i), (ii) y (iii) son problemas indecidibles
(C) Solo (i) y (ii) son problemas indecidibles
(D) Solo ( i) y (iii) son problemas indecidibles
Respuesta: (A)
Explicación: Se dice que un problema de decisión P es decidible (es decir, tiene un algoritmo) si el lenguaje L de todas las instancias sí a P es decidible.
El problema de pertenencia de un autómata finito finito es decidible .
Sólo (ii) y (iii) son problemas indecidibles.
La opción (A) 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