En la teoría de autómatas , la clase de gramáticas no restringidas (también llamadas gramáticas semi-Thue , type-0 o de estructura de frases ) 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 enumerables recursivamente arbitrarios .
Definicion formal
Una gramática sin restricciones es una gramática formal. , dónde es un conjunto finito de símbolos no terminales, es un conjunto finito de símbolos terminales , y son disjuntos, [nota 1] es un conjunto finito de reglas de producción de la forma dónde y son cadenas de símbolos en y no es la cadena vacía, y 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 no restringidas. [nota 2]
Equivalencia a las máquinas de Turing
Las gramáticas no restringidas caracterizan a los lenguajes enumerables recursivamente. Esto es lo mismo que decir que para cada gramática irrestrictaexiste alguna máquina de Turing capaz de reconocery viceversa. Dada una gramática sin restricciones, tal máquina de Turing 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.prueba, y la máquina utiliza la segunda cinta para generar formas oracionales a partir de. La máquina de Turing luego hace lo siguiente:
- Comience a la izquierda de la segunda cinta y elija repetidamente moverse hacia la derecha o seleccione la posición actual en la cinta.
- Nondeterministically elegir una producción de las producciones en .
- Si aparece en alguna posición en la segunda cinta, reemplace 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 , mueva los símbolos de la cinta a la izquierda).
- 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 es así, 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 del último paso se ejecuta un número arbitrario de veces, por lo que el idioma debe ser recursivamente enumerable.
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 usa solo producciones con uno o más símbolos no terminales en sus lados izquierdos. Por lo tanto, una gramática arbitraria sin restricciones siempre se puede convertir de manera equivalente para obedecer a 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 cadena dadapuede ser generado por una gramática sin restricciones dada es equivalente al problema de si puede ser aceptado por la máquina de Turing equivalente a la gramática. El último problema se denomina problema de detención y es indecidible.
Los lenguajes recursivamente enumerables se cierran bajo la estrella de Kleene , la concatenación , la unión y la intersección , pero no bajo la diferencia de conjuntos ; consulte Lenguaje recursivamente enumerable # Propiedades de cierre .
La equivalencia de las gramáticas irrestrictas a las máquinas de Turing implica la existencia de una gramática universal irrestricta, una gramática capaz de aceptar cualquier otro lenguaje gramatical irrestricto dada una descripción del lenguaje. Por esta razón, teóricamente es posible construir un lenguaje de programación basado en gramáticas no restringidas (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
- ^ En realidad, esto no es estrictamente necesario ya que las gramáticas no restringidas no hacen una distinción real entre las dos. La designación existe puramente para que se sepa cuándo dejar de generar formas oracionales de la gramática; más precisamente, el idioma reconocido por está restringido a cadenas de símbolos terminales
- ↑ Aunque Hopcroft y Ullman (1979) no mencionan las cardinalidades de, , explícitamente, la demostración de su Teorema 9.3 (construcción de una máquina de Turing equivalente a partir de una gramática no restringida dada, p.221, cf. Sección # Equivalencia a las máquinas de Turing ) requiere tácitamente la finitud de y longitudes finitas de todas las cadenas en reglas de . Cualquier miembro de o eso no ocurre en se puede omitir sin afectar el idioma generado.
Referencias
- ^ a b c d 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. CS1 maint: parámetro desalentado ( enlace )