Lenguaje recursivo

En matemáticas, lógica y ciencias de la computación, un lenguaje formal (un conjunto de secuencias finitas de símbolos tomados de un alfabeto fijo) es llamado lenguaje recursivo si es un subconjunto recursivo del conjunto de todas las secuencias finitas posibles sobre el alfabeto del lenguaje. Es decir, un lenguaje formal es recursivo si existe una máquina de Turing que siempre se detiene cuando dada una secuencia finita de símbolos del alfabeto del lenguaje —llamada cadena de caracteres o palabra— como entrada, acepta solo esas palabras que son parte del lenguaje y rechaza todas las otras palabras. Los lenguajes recursivos también se denominan lenguajes decidibles.

El concepto de decidibilidad puede ser extendido a otros modelos de computación. Por ejemplo, se puede hablar de lenguajes decidibles en una máquina de Turing no determinista. Por lo tanto, cuando hay ambigüedad, el sinónimo usado para "lenguaje recursivo" es lenguaje Turing-decidible, en vez de simplemente "lenguaje decidible".

La clase de todos los lenguajes recursivos es a menudo llamada R, aunque este nombre también es usado para la clase RP.

Este tipo de lenguaje no estaba definido en la jerarquía de Chomsky. Todos los lenguajes recursivos son también recursivamente enumerables. Todos los lenguajes regulares, libres de contexto y sensibles al contexto son lenguajes recursivos.

Propiedades de Clausura

Los lenguajes recursivos son cerrados bajo las siguientes operaciones. Sean L y P lenguajes recursivos, entonces los siguientes lenguajes son recursivos:

La Cerradura de Kleene $L^{*}$ .
La imagen de φ(L) bajo un morfismo e-libre φ.
La concatenación $L\circ P$ .
La unión $L\cup P$ .
La intersección $L\cap P$ .
El complemento de $L$ .
La diferencia simétrica L Δ P.
La diferencia $L-P$ .

La última propiedad viene del hecho que el conjunto diferencia puede ser expresado con intersecciones y complementos.

Véase también

Bibliografía

Michael Sipser (1997). «Decidability». Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 0-534-94728-X.
Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control 2 (2): 137-167. doi:10.1016/S0019-9958(59)90362-6.

Datos: Q1455907