# 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:
* 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.
* Triar una regla de producció $\beta \to \gamma$ de $G$ de forma no-determinista.
* 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$
* 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

## Referències

* 1 2 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. 2a edició. Boston: Addison-Wesley, 2001. ISBN 0201441241.
* 1 2 3 4 Alan., Parkes,. Introduction to languages, machines and logic : computable languages, abstract machines and formal logic. Londres: Springer, 2002. ISBN 1852334649.
* ↑ «Thue - Esolang». [Consulta: 26 desembre 2018].
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :