lenguaje recursivo

En matemáticas, lógica y ciencias de la computación, un lenguaje formal (un conjunto de secuencias finitas de tomados de un fijo) es llamado lenguaje recursivo si es un 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 . 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 . 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, y sensible al contexto son lenguajes recursivos.