Lenguaje recursivamente enumerable

En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.

DefiniciónEditar

Aunque existen varias definiciones equivalentes, ésta es una de las principales:

  1. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.

Todos los lenguajes regulares, independientes de contexto, dependientes de contexto y recursivos son recursivamente enumerables.

Propiedades de cierreEditar

Los lenguajes recursivamente enumerables son cerrados con las siguientes operaciones. Esto es, si   y   son dos lenguajes recursivamente enumerables, entonces los siguiente lenguajes son recursivamente enumerables también:

  • el cierre estrella   de  
  • la concatenación   de   y  
  • la unión   de   y  
  • la intersección   de   y  

Nótese que los lenguajes recursivamente enumerables no son cerrados con la diferencia ni el complementario.

  •   puede no ser recursivamente enumerable
  •   es recursivamente enumerable si y solo si   es también recursivo.

Véase tambiénEditar