En informática , una gramática se denomina 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 a través de 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 recursivas y es la recursión la que permite la producción de conjuntos infinitos de palabras. [1]
Una gramática no recursiva sólo puede producir un lenguaje finito; y cada lenguaje finito puede ser producido por una gramática no recursiva. [1] Por ejemplo, una gramática de línea recta produce sólo una palabra.
Una gramática recursiva libre de contexto que no contiene reglas inútiles produce necesariamente un lenguaje infinito. Esta propiedad constituye la base de un algoritmo que puede comprobar de manera eficiente si una gramática libre de contexto produce un lenguaje finito o infinito. [4]