¿Cuál de las siguientes afirmaciones es falsa?
(A) Cada NFA se puede convertir en un DFA equivalente
(B) Cada máquina de Turing no determinista se puede convertir en una máquina de Turing determinista equivalente
(C) Cada lenguaje regular es también un lenguaje libre de contexto
(D) Cada subconjunto de un el conjunto recursivamente enumerable es recursivo
Respuesta: (D)
Explicación:
un idioma es recursivamente enumerable si existe una máquina de Turing que acepta todas las strings del idioma y no acepta strings que no están en el idioma.
Las strings que no están en el idioma pueden ser rechazadas o pueden hacer que la máquina de Turing entre en un bucle infinito.
Un lenguaje recursivo no puede entrar en un bucle infinito, tiene que rechazar claramente la string, pero un lenguaje enumerable recursivamente puede entrar en un bucle infinito.
Entonces, cada lenguaje recursivo también es recursivamente enumerable.
Por lo tanto, la declaración ‘Todo subconjunto de un conjunto recursivamente enumerable es recursivo’ es falsa.
Por lo tanto, la opción (D) es la respuesta.
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