¿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:
- (A) Esto es decidible porque dada una máquina de Turing M, una string s y un entero k, M acepta que s dentro de k pasos se detenga o no, pero decidirá dentro de k pasos.
- (B) La equivalencia de dos máquinas de Turing es indecidible porque los lenguajes recursivos enumerables no están cerrados bajo el complemento.
- (C) El lenguaje aceptado por una máquina de estado finito dada no está vacío es definitivamente decidible, ya que siempre podemos minimizar el DFA y ver si es un estado único sin estado de aceptación
- (D) El lenguaje generado por una gramática libre de contexto no está vacío y también es decidible para esto tenemos un algoritmo.
La opción (B) 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