# Llenguatge recursiu

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge recursiu és un subconjunt recursiu del conjunt de totes les seqüències finites possibles de l'alfabet del llenguatge. Un llenguatge es recursiu si existeix una màquina de Turing que sempre s'atura quan rep una paraula del llenguatge com entrada, ja sigui per acceptar-la o per rebutjar-la. També s'anomenen llenguatges decidibles.
La classe de tots els llenguatges recursius s'anomena R.
Aquest tipus de llenguatge no està definit a la jerarquia de Chomsky. Tots els llenguatges recursius son també enumerables recursivament. Tots els llenguatges regulars, lliures de context i sensibles al context son llenguatges recursius.

## Definició

Hi ha dues definicions equivalents pel concepte de llenguatge recursiu:
* Un llenguatge recursiu és un subconjunt recursiu del conjunt de totes les possibles paraules de l'alfabet d'un llenguatge.
* Un llenguatge recursiu és un llenguatge formal pel qual existeix una màquina de Turing que, quan rep qualsevol entrada finita, sempre s'atura i accepta o rebutja l'entrada segons si la paraula es del llenguatge.
Per la definició 2, qualsevol problema de decisió es pot demostrar si és decidible dissenyant un algorisme que sempre s'atura per qualsevol entrada.

## Propietats de Clausura

Els llenguatges recursius son tancats segons les següents operacions. Sigui L i P dos llenguatges recursius, llavors el resultat d'aquestes operacions també ho son:
* Clausura de Kleene $L^{*}$
* La imatge φ(L) amb un homomorfisme
* La concatenació $L\circ P$
* La unió $L\cup P$
* La intersecció $L\cap P$
* El complement de L
* El conjunt diferència L-P

## Vegeu també

* Complexitat computacional

## Referències

* ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
* ↑ Immerman, Neil. Computability and Complexity. Spring 2016. Metaphysics Research Lab, Stanford University, 2016.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :