# Gramàtica recursiva

En lingüística i informàtica, una gramàtica es diu informalment que és una gramàtica recursiva si conté regles de producció que son recursives, és a dir, que expandint un símbol no-terminal seguint una regla pot portar a una cadena que conté el mateix símbol no terminal. Si no els conté, se'n diu una gramàtica no recursiva.
Per exemple, una gramàtica lliure de context és recursiva per l'esquerra si existeix un símbol no-terminal A tal que alguna de les regles de producció permet que es generi una cadena amb el símbol A (com a símbol més a l'esquerra). Totes les gramàtiques de la jerarquia de Chomsky poden ser recursives i és la recursivitat el que permet la producció de conjunts infinits de paraules.

## Propietats

Una gramàtica no recursiva només pot produir un llenguatge finit, i cada llenguatge finit es pot produir per una gramàtica no recursiva.
Una gramàtica lliure del context recursiva que no conté regles innecessàries produeix un llenguatge infinit. Aquesta propietat forma la base d'un algorisme que permet saber de manera eficient si una gramàtica lliure de context produeix un llenguatge finit o infinit.

## Referències

* 1 2 3 Nederhof, Mark-Jan; Satta, Giorgio «Parsing Non-recursive Context-free Grammars». Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02). Association for Computational Linguistics [Stroudsburg, PA, USA], 2002, pàg. 112–119. DOI: 10.3115/1073083.1073104.
* ↑ Power, James «Còpia arxivada». Notes on Formal Language Theory and Parsing, 2002. Arxivat de l'original el 2017-08-28 [Consulta: 31 desembre 2018].
* ↑ Moore, Robert C. «Removing Left Recursion from Context-free Grammars». NAACL 2000 Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. Association for Computational Linguistics [Stroudsburg, PA, USA], 2000, pàg. 249–255.
* ↑ Charles., Fleck, Arthur. Formal models of computation : the ultimate limits of computing. Singapore: World Scientific, 2001. ISBN 9810245009.
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. :