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.