Lenguajes recursivos y recursivos enumerables en TOC – Part 1

Enumerable recursivo (RE) o Tipo -0 Idioma

Los lenguajes RE o lenguajes de tipo 0 son generados por gramáticas de tipo 0. La máquina de Turing puede aceptar o reconocer un idioma RE, lo que significa que entrará en el estado final para las strings de idioma y puede o no entrar en el estado de rechazo para las strings que no forman parte del idioma. Significa que TM puede repetir para siempre las strings que no forman parte del idioma. Los idiomas RE también se denominan idiomas reconocibles de Turing.

Lenguaje recursivo (REC)

La máquina de Turing puede decidir un lenguaje recursivo (subconjunto de RE), lo que significa que entrará en el estado final para las strings de lenguaje y en el estado de rechazo para las strings que no forman parte del lenguaje. p.ej; L= {a ⁿ b ⁿ c ⁿ |n>=1} es recursivo porque podemos construir una máquina de turing que se moverá al estado final si la string tiene la forma a ⁿ b ⁿ c ⁿ de lo contrario se moverá al estado no final . Entonces, la TM siempre se detendrá en este caso. Los lenguajes REC también se denominan lenguajes decidibles de Turing. La relación entre los lenguajes RE y REC se puede mostrar en la Figura 1. 
 

 

Propiedades de cierre de lenguajes recursivos

• Unión : Si L1 y Si L2 son dos lenguajes recursivos, su unión L1∪L2 también será recursiva porque si TM se detiene por L1 y se detiene por L2, también se detendrá por L1∪L2.
• Concatenación: Si L1 y L2 son dos lenguajes recursivos, su concatenación L1.L2 también será recursiva. Por ejemplo: 

    L1= {anbncn|n>=0} 
    L2= {dmemfm|m>=0}
    L3= L1.L2
    = {anbncndm emfm|m>=0 and n>=0} is also recursive.

• L1 dice n no. de a seguido de n no. de b seguido de n no. de c L2 dice m no. de d seguido de m no. de e seguido de m no. de f Su concatenación primero coincide con no. de a’s, b’s y c’s y luego coincide con no. de d, e y f. Entonces puede ser decidido por TM.
• Cierre Kleene: Si L1 es recursivo, su cierre kleene L1* también será recursivo. Por ejemplo:

         L1= {anbncn|n>=0}
         L1*= { anbncn||n>=0}* is also recursive.

• Intersección y complemento : Si L1 y Si L2 son dos lenguajes recursivos, su intersección L1 ∩ L2 también será recursiva. Por ejemplo: 

    L1= {anbncndm|n>=0 and m>=0} 
    L2= {anbncndn|n>=0 and m>=0}
    L3=L1 ∩ L2
    = { anbncndn |n>=0} will be recursive.

 

L1 dice n no. de a seguido de n no. de b seguido de n no. de c y luego cualquier no. de d’s. L2 dice cualquier no. de a seguido de n no. de b seguido de n no. de c seguido de n no. de d’s. Su intersección dice n no. de a seguido de n no. de b seguido de n no. de c seguido de n no. de d’s. Entonces puede ser decidido por la máquina de turing, por lo tanto, recursivo. 
De manera similar, el complemento del lenguaje recursivo L1 que es ∑*-L1, también será recursivo.

Nota: A diferencia de los idiomas REC, los idiomas RE no están cerrados bajo la complementación, lo que significa que el complemento del idioma RE no necesita ser RE.

Preguntas GATE 

Pregunta 1: ¿Cuál de las siguientes afirmaciones es/son FALSA?  
1.Para cada TM no determinista, existe una TM determinista equivalente. 
2.Turing lenguas reconocibles se cierran bajo unión y complementación. 
3. Las lenguas decidibles de Turing se cierran bajo intersección y complementación. 
4. Los lenguajes reconocibles de Turing están cerrados bajo unión e intersección.

A.1 y 4 
B.1 y 3 
C.2 
D.3

Solución:

La declaración 1 es verdadera ya que podemos convertir cada TM no determinista en TM determinista. 
La declaración 2 es falsa ya que los lenguajes reconocibles de Turing (lenguas RE) no están cerrados bajo la complementación. 
La declaración 3 es verdadera ya que los lenguajes decidibles de Turing (lenguajes REC) están cerrados bajo intersección y complementación. 
La declaración 4 es verdadera ya que los lenguajes reconocibles de Turing (lenguas RE) están cerrados bajo unión e intersección.

Pregunta 2: Sea L una lengua y L’ su complemento. ¿Cuál de las siguientes NO es una posibilidad viable?  
A. Ni L ni L’ son RE. 
B. Uno de L y L’ es RE pero no recursivo; el otro no es RE. 
C.Tanto L como L’ son RE pero no recursivos. 
D.Tanto L como L’ son recursivos.

Solución:

La opción A es correcta porque si L no es RE, su complementación no será RE. La opción B es correcta porque si L es RE, L’ no necesita ser RE o viceversa porque los lenguajes RE no están cerrados bajo complementación. 
La opción C es falsa porque si L es RE, L’ no será RE. Pero si L es recursivo, L’ también lo será y ambos serán RE porque los lenguajes REC son un subconjunto de RE. Como han mencionado para no ser REC, la opción es falsa. 
La opción D es correcta porque si L es recursivo L’ también lo será.

Pregunta 3: Sea L1 un lenguaje recursivo, y sea L2 un lenguaje enumerable recursivamente pero no recursivo. ¿Cuál de las siguientes es VERDADERA?

A.L1′ es recursiva y L2′ es recursivamente enumerable 
B.L1′ es recursiva y L2′ no recursivamente enumerable 
C.L1′ y L2′ son recursivamente enumerables 
D.L1′ es recursivamente enumerable y L2′ es recursiva 
Solución:

La opción A es falsa ya que L2 ‘no puede ser enumerable recursivamente (L2 es RE y RE no están cerrados bajo complementación). 
La opción B es correcta ya que L1′ es REC (los lenguajes REC están cerrados bajo complementación) y L2′ no es enumerable recursivamente (los lenguajes RE no están cerrados bajo complementación). 
La opción C es falsa ya que L2 ‘no puede ser enumerable recursivamente (L2 es RE y RE no están cerrados bajo complementación). 
La opción D es falsa ya que L2 ‘no puede ser enumerable recursivamente (L2 es RE y los idiomas RE no están cerrados bajo complementación). Como los idiomas REC son un subconjunto de RE, L2 ‘no puede ser REC también.

Este artículo es una contribución de Sonal Tuteja . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.