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 una ambigüedad es posible, 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 sensible al contexto son lenguajes recursivos.