Gramàtica sense restriccions

En la teoria dels llenguatges formals, la classe de les gramàtiques sense restriccions (també dites semi-Thue, de tipus 0 o gramàtiques amb estructures de frase) és la classe més general de gramàtiques segons la jerarquia de Chomsky. Les produccions d'una gramàtica sense restriccions no tenen cap restricció a part que la part esquerra no estigui buida. Aquesta classe de gramàtiques poden generar llenguatges enumerables recursivament.

Definició formal

Una gramàtica sense restriccions és una gramàtica formal $G=(N,\Sigma ,P,S)$ on $N$ és un conjunt de símbols no terminals, $\Sigma$ és un conjunt de símbols terminals, $N$ i $\Sigma$ són disjunts. $P$ és un conjunt de regles de producció de la forma $\alpha \to \beta$ on $\alpha$ i $\beta$ son cadenes de símbols de $N\cup \Sigma$ i $\alpha$ no és la cadena buida, i $S\in N$ és un símbol especial d'inici. Com el seu nom indica, no hi ha restriccions a les regles de producció d'aquestes gramàtiques.

Equivalència a màquines de Turing

Les gramàtiques sense restriccions caracteritzen els llenguatges enumerables recursivament. Això és equivalent a dir que per cada gramàtica sense restricció $G$ existeix una màquina de Turing capaç de reconèixer $L(G)$ i viceversa. Donada una gramàtica sense restriccions, es pot construir una màquina de Turing no determinista amb dues cintes de forma molt senzilla. La primera cinta conté la paraula d'entrada $w$ a comprovar, i la segona cinta l'utilitza la màquina per generar sentències de $G$. La màquina de Turing ha de fer el següent:

1. Començar a l'esquerra de la segona cinta i triar moure's cap a la dreta o seleccionar la posició actual de la cinta.
2. Triar una regla de producció $\beta \to \gamma$ de $G$ de forma no-determinista.
3. SI $\beta$ apareix en alguna posició de la segona cinta, reemplaçar-la per $\gamma$ en aquell punt, potser desplaçant la resta de símbols de la cinta cap a la dreta o l'esquerra segona les longituds de $\beta$ i de $\gamma$
4. Comparar el resultat de la cinta 2 amb la paraula d'entrada de la cinta 1. Si son iguals, la màquina de Turing accepta l'entrada i s'atura, si no, la màquina torna al pas 1.

És senzill de veure que aquesta màquina generarà totes les sentències de $G$ i només aquestes a la segona cinta després que l'últim pas s'hagi executat un nombre arbitrari de cops., per tant el llenguatge $L(G)$ és enumerable recursivament.

La construcció a la inversa és possible. Donada una màquina de Turing, és possible generar la gramàtica sense restriccions equivalent que només fa servir regles de producció amb un o més símbols no-terminals a la seva part esquerra. Per tant, una gramàtica sense restricció qualsevol es pot convertir en una d'equivalent que obeeixi aquesta regla generant primer la màquina de Turing equivalent i després convertint la màquina en una gramàtica.

Propietats computacionals

El problema de decisió de saber si una cadena $s$es pot generar per una gramàtica sense restriccions és equivalent al problema de si la màquina de Turing equivalent a la gramàtica accepta la paraula. Aquest últim problema es coneix com el problema de la parada i es indecidible.

Els llenguatges enumerables recursivament son tancats per la clausura de Kleene, concatenació, unió i intersecció, però no per la diferència de conjunts.

L'equivalència entre gramàtiques sense restriccions i màquines de Turing implica l'existència d'una gramàtica sense restriccions universal, una gramàtica capaç d'acceptar qualsevol altre llenguatge descrit per una gramàtica sense restriccions. Per aquesta raó, teòricament és possible dissenyar un llenguatge de programació basat en gramàtiques sense restriccions (com per exemple el llenguatge de programació Thue).

Vegeu també

• Jerarquia de Chomsky
• Llenguatges formals
• Càlcul lambda