Gramática ilimitada

Teoría del lenguaje

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

Definicion formal

Una gramática irrestricta 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 disjunto , ^{[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 a las máquinas de Turing

Las gramáticas ilimitadas caracterizan los lenguajes recursivamente enumerables. Esto es lo mismo que decir que por cada gramática ilimitada existe alguna máquina de Turing capaz de reconocerla y viceversa. Dada una gramática ilimitada, una máquina de Turing de este tipo es bastante sencilla 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 máquina utiliza la segunda cinta para generar formas de oraciones a partir de . La máquina de Turing hace entonces 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 de . ${\displaystyle \beta \to \gamma }$ ${\displaystyle G}$
3. Si aparece en alguna posición de la segunda cinta, reemplácela por en ese punto, posiblemente desplazando los símbolos de la cinta hacia la izquierda o hacia la derecha dependiendo de las longitudes relativas de y (por ejemplo, si es más largo que , mueva 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 de oración resultante en la cinta 2 con la palabra en la cinta 1. Si coinciden, entonces la máquina de Turing acepta la palabra. Si no lo hacen, 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 un número arbitrario de veces, por lo que el lenguaje debe ser recursivamente enumerable. ${\displaystyle G}$ ${\displaystyle L(G)}$

También es posible la construcción inversa. Dada alguna máquina de Turing, es posible crear una gramática equivalente sin restricciones ^{[1] : 222} que incluso utilice sólo producciones con uno o más símbolos no terminales en su lado izquierdo. Por lo tanto, una gramática arbitraria sin restricciones siempre puede convertirse de manera equivalente para obedecer a la última forma, convirtiéndola a una máquina de Turing y viceversa. Algunos autores ^{[ cita requerida ]} utilizan esta última forma como definición de gramática ilimitada .

Propiedades computacionales

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

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

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

Ver también

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

Notas

1. En realidad, no es estrictamente necesario ya que las gramáticas ilimitadas no hacen una distinción real entre las dos. 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. Si bien 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 a las máquinas de Turing) requiere tácitamente la finitud y las longitudes finitas de todas las cadenas en las reglas de . Cualquier miembro de o que no aparezca en se puede omitir 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, los lenguajes y la computación de los autómatas (1ª ed.). Addison-Wesley. ISBN 0-201-44124-1.