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.[1][2]

Definició formalModifica

Una gramàtica sense restriccions és una gramàtica formal   on   és un conjunt de símbols no terminals,   és un conjunt de símbols terminals,   i   són disjunts.   és un conjunt de regles de producció de la forma   on   i   son cadenes de símbols de   i   no és la cadena buida, i   é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.[2]

Equivalència a màquines de TuringModifica

Les gramàtiques sense restriccions caracteritzen els llenguatges enumerables recursivament. Això és equivalent a dir que per cada gramàtica sense restricció   existeix una màquina de Turing capaç de reconèixer   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   a comprovar, i la segona cinta l'utilitza la màquina per generar sentències de  . La màquina de Turing ha de fer el següent:[1]

  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ó   de   de forma no-determinista.
  3. SI   apareix en alguna posició de la segona cinta, reemplaçar-la per   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   i de  
  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   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   é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.[2]

Propietats computacionalsModifica

El problema de decisió de saber si una cadena  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.[2]

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).[3]

Vegeu tambéModifica

ReferènciesModifica

  1. 1,0 1,1 1939-, Hopcroft, John E.,. Introduction to automata theory, languages, and computation. 2nd ed. Boston: Addison-Wesley, 2001. ISBN 0201441241. 
  2. 2,0 2,1 2,2 2,3 Alan., Parkes,. Introduction to languages, machines and logic : computable languages, abstract machines and formal logic. Londres: Springer, 2002. ISBN 1852334649. 
  3. «Thue - Esolang». [Consulta: 26 desembre 2018].