¿Cuál de los siguientes no es decidible?
(A) Dada una máquina de Turing M, una string s y un entero k, M acepta s en k pasos
(B) Equivalencia de dos máquinas de Turing dadas
(C) El lenguaje aceptado por una máquina de estados finitos dada no está vacío
(D) Lenguaje generado por una gramática libre de contexto no está vacío
Respuesta: (B)
Explicación:
prueba de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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