PUERTA | PUERTA CS 2021 | Conjunto 1 | Pregunta 22

Sea ⟨M⟩ una codificación de un autómata M. Supongamos que Σ={0,1}. ¿Cuál de los siguientes lenguajes es/NO son recursivos?
(A) L = {⟨M⟩ ∣ M es un DFA tal que L(M)=∅}
(B) L = {⟨M⟩ ∣ M es un DFA tal que L(M)=Σ*}
(C) L = {⟨M⟩ ∣ M es un PDA tal que L(M)=∅}
(D) L = {⟨M⟩ ∣ M es un PDA tal que L(M)=Σ*}

Respuesta: (D)
Explicación : lenguaje recursivo (REC)– Se dice que un lenguaje ‘L’ es recursivo si existe una máquina de Turing que aceptará todas las strings en ‘L’ y rechazará todas las strings que no estén en ‘L’. La máquina de Turing se detendrá cada vez y dará una respuesta (aceptada o rechazada) para todas y cada una de las entradas de string. Un lenguaje ‘L’ es decidible si es un lenguaje recursivo. Todos los lenguajes decidibles son lenguajes recursivos y viceversa.

De las opciones dadas, L = {⟨M⟩ ∣ M es un PDA tal que L(M)=Σ*} es un problema de completitud de CFL, que es indecidible. Por lo tanto, no recursivo.

Dado un idioma L, tome su complemento L’ y verifique si L’ está vacío => L está completo.
Dado que las lámparas fluorescentes compactas no están cerradas bajo complementación. Por lo tanto, la integridad es indecidible para CFL.
Cuestionario de esta pregunta