Lenguaje recursivo

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.La clase de todos los lenguajes recursivos es a menudo llamada R, aunque este nombre también es usado para la clase RP.Todos los lenguajes regulares, libres de contexto y sensibles al contexto son lenguajes recursivos.Los lenguajes recursivos son cerrados bajo las siguientes operaciones.Sean L y P lenguajes recursivos, entonces los siguientes lenguajes son recursivos: La última propiedad viene del hecho que el conjunto diferencia puede ser expresado con intersecciones y complementos.