Lenguaje recursivo

En lógica matemática e informática , un lenguaje recursivo es un tipo de lenguaje formal , también llamado decidible , o decidible de Turing . La clase de todos los lenguajes recursivos a menudo se denota por R , aunque se usa la misma designación para la clase RP .

Este tipo de lenguaje no está definido en la jerarquía de Chomsky ( Chomsky 1959 ).

Definiciones

Se utilizan dos definiciones equivalentes de un lenguaje recursivo:

1. Un lenguaje recursivo formal es un subconjunto recursivo del conjunto de todas las palabras posibles en el alfabeto de un lenguaje formal .
2. Un lenguaje recursivo es un lenguaje formal para el cual existe una máquina de Turing que se detiene en cualquier cadena de entrada y la permite si y solo si pertenece al lenguaje. Se dice que una máquina de este tipo es un solucionador y resuelve el lenguaje recursivo dado.

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

Propiedades de cierre

Los lenguajes recursivos se cierran en las siguientes operaciones. Así, si L y P son lenguajes recursivos, entonces los siguientes lenguajes también lo son:

• Cierre Kleene ;
• la imagen de , donde es un homomorfismo tal que , donde es una cadena vacía;
• concatenación ;
• asociación ;
• intersección ;
• adición ;
• diferencia _

Referencias

• Michael Sipser Decidibilidad // Introducción a la Teoría de la  Computación . - PWS Publishing, 1997. - P.  151 -170. — ISBN 0-534-94728-X .
• Chomsky, Noam. Sobre ciertas propiedades formales de las gramáticas   // Información y Control : diario. - 1959. - Vol. 2 , núm. 2 . - pág. 137-167 . - doi : 10.1016/S0019-9958(59)90362-6 .

Véase también

• Lenguaje enumerado recursivamente