Lenguaje enumerado recursivamente

En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal, también conocido como parcialmente decidible o reconocible de Turing . En la jerarquía de Chomsky , se le conoce como lenguaje tipo 0. La clase de todos los lenguajes recursivamente enumerables se denomina RE.

Definiciones

Hay tres definiciones equivalentes principales del concepto de un lenguaje recursivamente enumerable.

1. Un lenguaje formal recursivamente enumerable es un subconjunto recursivamente enumerable del conjunto de todas las palabras posibles sobre el alfabeto del lenguaje .
2. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing (u otra función computable ) que enumera todas las cadenas válidas del lenguaje. Tenga en cuenta que si el idioma es infinito, entonces se puede elegir un algoritmo de enumeración que evite las repeticiones, ya que para una cadena numerada n se puede verificar si "ya" se ha devuelto en un número menor que n . Si lo hubo, use el número de salida n+1 en su lugar (recursivamente), verificando nuevamente si es "nuevo".
3. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual hay una máquina de Turing (u otra función computable ) que se detendrá y aceptará cualquier cadena de entrada del lenguaje, pero se detendrá y rechazará o no se detendrá en absoluto para cualquier cadena de entrada que no sea del lenguaje. . Los lenguajes recursivos requieren que la máquina de Turing se detenga de todos modos.

Todos los lenguajes regulares, libres de contexto, sensibles al contexto y recursivos son recursivamente enumerables.

El teorema de Post muestra que el RE, junto con el co-RE adicional, corresponden al primer nivel de la jerarquía aritmética .

Propiedades de cierre

Los lenguajes recursivamente enumerables se cierran bajo las siguientes operaciones. Sean L y P  dos lenguajes recursivamente enumerables, entonces los siguientes lenguajes también son recursivamente enumerables:

• Kleene estrella de L
• concatenación de L y P
• una asociación
• intersección

Tenga en cuenta que los lenguajes recursivamente enumerables no se cierran bajo diferencia o complemento. La diferencia de conjuntos L \ P puede o no ser enumerable recursivamente. Si L es recursivamente enumerable, entonces el complemento de L es recursivamente enumerable si y solo si L también es recursivo.

Literatura

Gladkiy A. V. Gramáticas y lenguajes formales. - M. : "Nauka", 1973. - 368 p.