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.[1]
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).[2][3] 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.[1]
Propietats
[modifica]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.[1]
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.[4]
Referències
[modifica]- ↑ 1,0 1,1 1,2 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.
| ||||||||||
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. | ||||||||||
