En ciencias de la computación , una gramática se llama informalmente gramática recursiva si contiene reglas de producción que son recursivas , lo que significa que expandir un no terminal de acuerdo con estas reglas puede eventualmente conducir a una cadena que incluya el mismo no terminal nuevamente. De lo contrario, se denomina gramática no recursiva . [1]
Por ejemplo, una gramática para un lenguaje libre de contexto se deja recursiva si existe un símbolo no terminal A que se puede pasar por las reglas de producción para producir una cadena con A (como el símbolo más a la izquierda). [2] [3] Todos los tipos de gramáticas en la jerarquía de Chomsky pueden ser recursivos y es la recursividad la que permite la producción de infinitos conjuntos de palabras. [1]
Propiedades
Una gramática no recursiva sólo puede producir un lenguaje finito; y cada lengua finita puede producirse mediante una gramática no recursiva. [1] Por ejemplo, una gramática de línea recta produce una sola palabra.
Una gramática recursiva libre de contexto que no contiene reglas inútiles produce necesariamente un lenguaje infinito. Esta propiedad forma la base de un algoritmo que puede probar de manera eficiente si una gramática libre de contexto produce un lenguaje finito o infinito. [4]
Referencias
- ↑ a b c Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Actas de la 40ª Reunión Anual de la Asociación de Lingüística Computacional (ACL '02) , Stroudsburg, PA, EE.UU .: Asociación de Lingüística Computacional, págs. 119, doi : 10.3115 / 1073083.1073104.
- ^ Notas sobre análisis y teoría del lenguaje formal , James Power, Departamento de Ciencias de la Computación de la Universidad Nacional de Irlanda, Maynooth Maynooth, Co. Kildare, Irlanda.
- ^ Moore, Robert C. (2000), "Removing Left Recursion from Context-free Grammars", Actas del primer capítulo norteamericano de la Conferencia de la Asociación de Lingüística Computacional (NAACL 2000) , Stroudsburg, PA, EE. UU .: Asociación de Lingüística Computacional, págs. 249-255.
- ^ Fleck, Arthur Charles (2001), Modelos formales de computación: Los límites últimos de la computación , serie AMAST en computación, 7 , World Scientific, Teorema 6.3.1, p. 309, ISBN 9789810245009.