Gramática sin restricciones

Teoría del lenguaje

En la teoría de autómatas , la clase de gramáticas sin restricciones (también llamadas gramáticas semi-Thue , de tipo 0 o de estructura sintagmática ) es la clase más general de gramáticas en la jerarquía de Chomsky . No se imponen restricciones a la producción de una gramática sin restricciones, salvo que cada uno de sus lados izquierdos no esté vacío. ^{[1] : 220} Esta clase de gramática puede generar lenguajes recursivamente enumerables arbitrarios .

Definición formal

Una gramática sin restricciones es una gramática formal , donde ${\textstyle G=(N,T,P,S)}$

• ${\displaystyle N}$es un conjunto finito de símbolos no terminales ,
• ${\displaystyle T}$es un conjunto finito de símbolos terminales con y disjuntos , ^{[nota 1]} ${\displaystyle N}$ ${\displaystyle T}$
• ${\displaystyle P}$es un conjunto finito de reglas de producción de la forma donde y son cadenas de símbolos en y no es la cadena vacía, y ${\displaystyle \alpha \to \beta ,}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle N\cup T}$ ${\displaystyle \alpha }$

• ${\displaystyle S\in N}$es un símbolo de inicio especialmente designado. ^{[1] : 220}

Como su nombre lo indica, no existen restricciones reales sobre los tipos de reglas de producción que pueden tener las gramáticas sin restricciones. ^{[nota 2]}

Equivalencia con las máquinas de Turing

Las gramáticas sin restricciones caracterizan a los lenguajes recursivamente enumerables. Esto es lo mismo que decir que para cada gramática sin restricciones existe alguna máquina de Turing capaz de reconocer y viceversa. Dada una gramática sin restricciones, una máquina de Turing de este tipo es lo suficientemente simple de construir, como una máquina de Turing no determinista de dos cintas . ^{[1] : 221} La primera cinta contiene la palabra de entrada que se va a probar, y la segunda cinta es utilizada por la máquina para generar formas oracionales a partir de . La máquina de Turing luego hace lo siguiente: ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle w}$ ${\displaystyle G}$

1. Comience a la izquierda de la segunda cinta y elija repetidamente moverse hacia la derecha o seleccionar la posición actual en la cinta.
2. Elija de forma no determinista una producción entre las producciones en . ${\displaystyle \beta \to \gamma }$ ${\displaystyle G}$
3. Si aparece en alguna posición en la segunda cinta, reemplácelo por en ese punto, posiblemente desplazando los símbolos en la cinta hacia la izquierda o hacia la derecha dependiendo de las longitudes relativas de y (por ejemplo, si es más largo que , desplaza los símbolos de la cinta hacia la izquierda). ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$
4. Compare la forma oracional resultante en la cinta 2 con la palabra en la cinta 1. Si coinciden, la máquina de Turing acepta la palabra. Si no, la máquina de Turing volverá al paso 1.

Es fácil ver que esta máquina de Turing generará todas y sólo las formas oracionales de en su segunda cinta después de que el último paso se ejecute una cantidad arbitraria de veces, por lo tanto, el lenguaje debe ser recursivamente enumerable. ${\displaystyle G}$ ${\displaystyle L(G)}$

La construcción inversa también es posible. Dada alguna máquina de Turing, es posible crear una gramática irrestricta equivalente ^{[1] : 222} que incluso utilice solo producciones con uno o más símbolos no terminales en sus lados izquierdos. Por lo tanto, una gramática irrestricta arbitraria siempre se puede convertir de manera equivalente para que obedezca la última forma, convirtiéndola en una máquina de Turing y viceversa. Algunos autores ^{[ cita requerida ]} utilizan la última forma como definición de gramática irrestricta .

Propiedades computacionales

El problema de decisión de si una determinada cadena puede ser generada por una determinada gramática sin restricciones es equivalente al problema de si puede ser aceptada por la máquina de Turing equivalente a la gramática. Este último problema se denomina problema de detención y es indecidible. ${\displaystyle s}$

Los lenguajes enumerables recursivamente están cerrados bajo estrella de Kleene , concatenación , unión e intersección , pero no bajo diferencia de conjuntos ; consulte Lenguaje enumerable recursivamente#Propiedades de cierre .

La equivalencia de las gramáticas sin restricciones con las máquinas de Turing implica la existencia de una gramática sin restricciones universal, una gramática capaz de aceptar el lenguaje de cualquier otra gramática sin restricciones dada una descripción del lenguaje. Por esta razón, es teóricamente posible construir un lenguaje de programación basado en gramáticas sin restricciones (por ejemplo, Thue).

Véase también

• Cálculo lambda
• Sistema Semi-Thue : no distingue entre símbolos terminales y no terminales, admite lados izquierdos vacíos

Notas

1. En realidad, no es estrictamente necesario, ya que las gramáticas sin restricciones no hacen una distinción real entre ambos. La designación existe únicamente para que uno sepa cuándo dejar de generar formas oracionales de la gramática; más precisamente, el lenguaje reconocido por está restringido a cadenas de símbolos terminales. ${\displaystyle T\cap N=\emptyset }$ ${\displaystyle L(G)}$ ${\displaystyle G}$
2. Aunque Hopcroft y Ullman (1979) no mencionan las cardinalidades de , , explícitamente, la prueba de su Teorema 9.3 (construcción de una máquina de Turing equivalente a partir de una gramática dada sin restricciones, p.221, cf. Sección #Equivalencia con máquinas de Turing) requiere tácitamente la finitud de y longitudes finitas de todas las cadenas en reglas de . Cualquier miembro de o que no ocurra en puede omitirse sin afectar el lenguaje generado. ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle P}$

Referencias

1. Hopcroft, John ; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-44124-1.