¿Cuáles de los siguientes problemas de decisión son indecidibles ?
(A) Solo I y IV
(B) Solo II y III
(C) Solo III y IV
(D) Solo II y IV
Respuesta: (C)
Explicación: Un problema es indecidible si hay ningún algoritmo para encontrar la solución para ello.
El enunciado I es un problema de disyunción de dos lenguajes regulares que son decidibles.
La Declaración-II es un problema de membresía de CFG que siempre es decidible.
La Declaración-III es un problema de equivalencia de dos gramáticas libres de contexto (CFG) que es indecidible.
Enunciado-IV, Dada una máquina de Turing M, es L(M) = Ф es un problema indecidible bien conocido, es decir, no RE. Pero si L(M) ≠ Ф es semidecidible, es decir, RE pero no REC.
Por tanto, sólo son decidibles los enunciados III y IV . La opción (C) 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