Gramática recursiva

En informática , una gramática se denomina informalmente gramática recursiva si contiene reglas de producción recursivas , lo que significa que expandir un no terminal según estas reglas puede eventualmente dar como resultado una cadena que incluya nuevamente el mismo no terminal. De lo contrario , se denomina gramática no recursiva . ^{[ 1 ]}

Por ejemplo, una gramática para un lenguaje libre de contexto es recursiva por la izquierda si existe un símbolo no terminal A que 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 recursión la que permite la producción de conjuntos infinitos de palabras. ^{[ 1 ]}

Una gramática no recursiva solo puede producir un lenguaje finito; y cada lenguaje finito puede ser producido por una gramática no recursiva. ^{[ 1 ]} Por ejemplo, una gramática lineal produce solo una sola palabra.

Una gramática libre de contexto recursiva que no contiene reglas inútiles produce necesariamente un lenguaje infinito. Esta propiedad constituye la base de un algoritmo que puede comprobar eficientemente si una gramática libre de contexto produce un lenguaje finito o infinito. ^{[ 4 ]}