¿Cuál de las siguientes afirmaciones es/son FALSA?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.
(A) 1 y 4 solamente
(B) 1 y 3 solamente
(C) 2 solamente
(D) 3 solamente
Respuesta: (C)
Explicación: Un reconocedor de un idioma es una máquina que reconoce ese idioma.
Un decisor de un idioma es una máquina que decide ese idioma.
Ambos tipos de máquinas se detienen en el estado Aceptar en strings que están en el idioma.
Un Decisor también se detiene si la string no está en el idioma
. Un Reconocedor PUEDE o NO PUEDE detenerse en strings que no están en el idioma.
En todas las entradas:
Un decisor DEBE detenerse (en estado de aceptación o rechazo)
Un reconocedor PUEDE o NO PUEDE detenerse en algunas strings (P: ¿Cuáles?)
Un lenguaje es decidible por Turing (o decidible) si alguna máquina de Turing lo decide. También conocido como lenguaje recursivo.
Un idioma es reconocible por Turing si alguna máquina de Turing lo reconoce. También conocido como lenguaje recursivamente enumerable.
Fuente: http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html
Los lenguajes recursivos (decidibles de Turing) se cierran siguiendo
la estrella de Kleene, la concatenación, la unión, la intersección, el complemento y la diferencia de conjuntos.
El lenguaje recursivamente enumerable se cierra bajo la estrella de Kleene, la concatenación, la unión, la intersección. NO están cerrados por complemento o diferencia de conjuntos.
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