Las gramáticas indexadas son una generalización de las gramáticas libres de contexto en las que los no terminales están equipados con listas de banderas o símbolos de índice . El lenguaje producido por una gramática indexada se denomina idioma indexado .
Definición
Definición moderna de Hopcroft y Ullman
En publicaciones contemporáneas siguientes Hopcroft y Ullman (1979), [2] una gramática indexada se define formalmente un 5-tupla G = ⟨ N , T , F , P , S ⟩ donde
- N es un conjunto de variables o símbolos no terminales ,
- T es un conjunto (" alfabeto ") de símbolos terminales,
- F es un conjunto de los llamados símbolos de índice , o índices ,
- S ∈ N es el símbolo de inicio y
- P es un conjunto finito de producciones .
Tanto en producciones como en derivaciones de gramáticas indexadas, se adjunta una cadena ("pila") σ ∈ F * de símbolos de índice a cada símbolo no terminal A ∈ N , denotado por A [ σ ]. [nota 1] Los símbolos de terminal no pueden ir seguidos de pilas de índices. Para una pila de índices σ ∈ F * y una cadena α ∈ ( N ∪ T ) * de símbolos no terminales y terminales, α [ σ ] denota el resultado de adjuntar [ σ ] a cada no terminal en α ; por ejemplo, si α es igual a B C d E con a , d ∈ T terminal, y B , C , E ∈ N símbolos no terminales, entonces α [ σ ] denota a B [ σ ] C [ σ ] d E [ σ ]. Usando esta notación, cada producción en P tiene que ser de la forma
- A [σ] → α [σ],
- A [σ] → B [ f σ], o
- A [ f σ] → α [σ],
donde A , B ∈ N son símbolos no terminales, f ∈ F es un índice, σ ∈ F * es una cadena de símbolos de índice y α ∈ ( N ∪ T ) * es una cadena de símbolos no terminales y terminales. Algunos autores escriben ".." en lugar de " σ " para la pila de índices en las reglas de producción; la regla de tipo 1, 2 y 3 dice A [..] → α [..], A [..] → B [ f ..] , y A [ f ..] → α [..] , respectivamente.
Las derivaciones son similares a las de una gramática libre de contexto, excepto por la pila de índices adjunta a cada símbolo no terminal. Cuando una producción como por ejemplo A [ σ ] → B [ σ ] C [ σ ] se aplica, la pila índice de A se copia en tanto B y C . Además, una regla puede empujar un símbolo de índice a la pila, o hacer estallar su símbolo de índice "superior" (es decir, más a la izquierda).
Formalmente, la relación ⇒ ("derivación directa") se define en el conjunto ( N [ F * ] ∪ T ) * de "formas oracionales" de la siguiente manera:
- Si A [ σ ] → α [ σ ] es una producción de tipo 1, entonces β A [ φ ] γ ⇒ β α [ φ ] γ , usando la definición anterior. Es decir, la pila de índices del lado izquierdo de la regla φ se copia en cada no terminal del lado derecho.
- Si A [ σ ] → B [ fσ ] es una producción de tipo 2, entonces β A [ φ ] γ ⇒ β B [ fφ ] γ . Es decir, la pila de índices del lado derecho se obtiene de la pila del lado izquierdo φ presionando f sobre ella.
- Si A [ fσ ] → α [ σ ] es una producción de tipo 3, entonces β A [ fφ ] γ ⇒ β α [ φ ] γ , usando nuevamente la definición de α [ σ ]. Es decir, el primer índice f se extrae de la pila del lado izquierdo, que luego se distribuye a cada no terminal del lado derecho.
Como de costumbre, la relación de derivación se define como el cierre transitivo reflexivo de la derivación directa ⇒. El idioma L ( G ) = { w ∈ T * : S w } es el conjunto de todas las cadenas de símbolos terminales derivables del símbolo de inicio.
Definición original de Aho
Históricamente, el concepto de gramáticas indexadas fue introducido por primera vez por Alfred Aho (1968) [3] utilizando un formalismo diferente. Aho definió una gramática indexada como una tupla de 5 ( N , T , F , P , S ) donde
- N es un alfabeto finito de variables o símbolos no terminales
- T es un alfabeto finito de símbolos terminales
- F ⊆ 2 N × ( N ∪ T ) * es el conjunto finito de las denominadas banderas (cada bandera es en sí misma un conjunto de las denominadas producciones de índice )
- P ⊆ N × ( NF * ∪ T ) * es el conjunto finito de producciones
- S ∈ N es el símbolo de inicio
Las derivaciones directas fueron las siguientes:
- Una producción p = ( A → X 1 η 1 … X k η k ) de P coincide con un A ∈ N no terminal seguido de su cadena (posiblemente vacía) de banderas ζ ∈ F * . En contexto, γ Aζ δ , vía p , deriva a γ X 1 θ 1 … X k θ k δ , donde θ i = η i ζ si X i era un no terminal y la palabra vacía en caso contrario. Por lo tanto, los indicadores antiguos de A se copian en cada nuevo no terminal producido por p . Cada una de estas producciones se puede simular mediante producciones apropiadas de tipo 1 y 2 en el formalismo Hopcroft / Ullman.
- Una producción de índice p = ( A → X 1 … X k ) ∈ f coincide con Afζ (la bandera f de la que proviene debe coincidir con el primer símbolo que sigue al no terminal A ) y copia la cadena de índice restante ζ a cada nuevo no terminal: γ Afζ δ deriva a γ X 1 θ 1 … X k θ k δ , donde θ i es la palabra vacía cuando X i es un terminal y ζ cuando es un no terminal. Cada una de estas producciones corresponde a una producción de tipo 3 en el formalismo Hopcroft / Ullman.
Este formalismo lo utiliza, por ejemplo, Hayashi (1973, p. 65-66). [4]
Ejemplos de
En la práctica, las pilas de índices pueden contar y recordar qué reglas se aplicaron y en qué orden. Por ejemplo, las gramáticas indexadas pueden describir el lenguaje sensible al contexto de las triples de palabras { www : w ∈ { a , b } * }:
S [ σ ] → S [ fσ ] T [ fσ ] → a T [ σ ] S [ σ ] → S [ gσ ] T [ gσ ] → b T [ σ ] S [ σ ] → T [ σ ] T [ σ ] T [ σ ] T [] → ε
Una derivación de abbabbabb es entonces
- S [] ⇒ S [ g ] ⇒ S [ gg ] ⇒ S [ fgg ] ⇒ T [ fgg ] T [ fgg ] T [ fgg ] ⇒ a T [ gg ] T [ fgg ] T [ fgg ] ⇒ ab T [ g ] T [ fgg ] T [ fgg ] ⇒ abb T [] T [ fgg ] T [ fgg ] ⇒ abb T [ fgg ] T [ fgg ] ⇒ ... ⇒ abb abb T [ fgg ] ⇒ ... ⇒ abb abb abb .
Como otro ejemplo, la gramática G = ⟨{ S , T , A , B , C }, { a , b , c }, { f , g }, P , S ⟩ produce el lenguaje { a n b n c n : n ≥ 1}, donde el conjunto de producción P consta de
S [ σ ] → T [ gσ ] A [ fσ ] → a A [ σ ] A [ gσ ] → a T [ σ ] → T [ fσ ] B [ fσ ] → b B [ σ ] B [ gσ ] → b T [ σ ] → A [ σ ] B [ σ ] C [ σ ] C [ fσ ] → c C [ σ ] C [ gσ ] → c
Un ejemplo de derivación es
- S [] ⇒ T [ g ] ⇒ T [ fg ] ⇒ A [ fg ] B [ fg ] C [ fg ] ⇒ aA [ g ] B [ fg ] C [ fg ] ⇒ aA [ g ] bB [ g ] C [ fg ] ⇒ aA [ g ] bB [ g ] cC [ g ] ⇒ aa bB [ g ] cC [ g ] ⇒ aa bb cC [ g ] ⇒ aa bb cc .
Ambos lenguajes de ejemplo no están libres de contexto por el lema de bombeo .
Propiedades
Hopcroft y Ullman tienden a considerar los lenguajes indexados como una clase "natural", ya que son generados por varios formalismos distintos de las gramáticas indexadas, a saber. [5]
- Autómatas de pila anidados unidireccionales de Aho [6]
- Macro gramáticas de Fischer [7]
- Autómatas de Greibach con pilas de pilas [8]
- Caracterización algebraica de Maibaum [9]
Hayashi [4] generalizó el lema de bombeo a gramáticas indexadas. Por el contrario, Gilman [10] [11] da un "lema que se encoge" para los lenguajes indexados.
Gramáticas indexadas lineales
Gerald Gazdar ha definido una segunda clase, las gramáticas indexadas lineales ( LIG ), [14] al exigir que a lo sumo un no terminal en cada producción especificarse como la recepción de la pila, [nota 2] , mientras que en una gramática indexada ordinario, todos los no terminales reciben copias de la pila. Formalmente, una gramática indexada lineal se define de manera similar a una gramática indexada ordinaria, pero los requisitos de forma de la producción se modifican para:
- A [ σ ] → α [] B [ σ ] β [],
- A [ σ ] → α [] B [ fσ ] β [],
- A [ fσ ] → α [] B [ σ ] β [],
donde A , B , f , σ , α se usan como arriba , y β ∈ ( N ∪ T ) * es una cadena de símbolos no terminales y terminales como α . [nota 3] Además, la relación de derivación directa ⇒ se define de manera similar a la anterior. Esta nueva clase de gramáticas define una clase de lenguajes estrictamente más pequeña, [15] que pertenece a las clases levemente sensibles al contexto .
El idioma { www : w ∈ { a , b } * } se puede generar mediante una gramática indexada, pero no mediante una gramática indexada lineal, mientras que tanto { ww : w ∈ { a , b } * } y { a n b n c n : n ≥ 1} son generables por una gramática indexada lineal.
Si se admiten tanto las reglas de producción originales como las modificadas, la clase de idioma sigue siendo el idioma indexado. [dieciséis]
Ejemplo
Dejando que σ denote una colección arbitraria de símbolos de pila, podemos definir una gramática para el lenguaje L = { a n b n c n | n ≥ 1} [nota 4] como
S [ σ ] → a S [ fσ ] c S [ σ ] → T [ σ ] T [ fσ ] → T [ σ ] b T [] → ε
Para derivar la cadena abc tenemos los pasos:
- S [] ⇒ aS [ f ] c ⇒ aT [ f ] c ⇒ aT [] bc ⇒ abc
Similar:
- S [] ⇒ aS [ f ] c ⇒ aaS [ ff ] cc ⇒ aaT [ ff ] cc ⇒ aaT [ f ] bcc ⇒ aaT [] bbcc ⇒ aabbcc
Potencia de cálculo
Los lenguajes indexados linealmente son un subconjunto de los lenguajes indexados y, por lo tanto, todos los LIG pueden recodificarse como IG, lo que hace que los LIG sean estrictamente menos potentes que los IG. La conversión de un LIG a un IG es relativamente simple. [17] Las reglas de LIG en general se parecen aproximadamente a, módulo la parte push / pop de una regla de reescritura. Los simbolos y representan cadenas de símbolos terminales y / o no terminales, y cualquier símbolo no terminal en cualquiera de ellos debe tener una pila vacía, según la definición de LIG. Esto, por supuesto, es contrario a cómo se definen los IG: en un IG, los no terminales cuyas pilas no se están empujando o sacando deben tener exactamente la misma pila que el no terminal reescrito. Por lo tanto, de alguna manera, necesitamos tener no terminales en y que, a pesar de tener pilas no vacías, se comportan como si tuvieran pilas vacías.
Considere la regla como un caso de ejemplo. Al convertir esto en un IG, el reemplazo de debe ser algo que se comporta exactamente como independientemente de que es. Para lograr esto, simplemente podemos tener un par de reglas que toman cualquier dónde no está vacío y saca símbolos de la pila. Luego, cuando la pila está vacía, se puede reescribir como.
Podemos aplicar esto en general para derivar un IG de un LIG. Entonces, por ejemplo, si la LIG para el idioma es como sigue:
La regla sentencial aquí no es una regla IG, pero usando el algoritmo de conversión anterior, podemos definir nuevas reglas para , cambiando la gramática a:
Cada regla ahora se ajusta a la definición de un IG, en el que todos los no terminales en el lado derecho de una regla de reescritura reciben una copia de la pila del símbolo reescrito. Por tanto, las gramáticas indexadas pueden describir todos los lenguajes que las gramáticas indexadas linealmente pueden describir.
Relación con otros formalismos
Vijay-Shanker y Weir (1994) [18] demuestra que Lineal indexado gramáticas, combinatoria categoriales Gramáticas , Árbol-contiguas Gramáticas y Cabeza gramáticas toda definen la misma clase de idiomas de cuerda. Su definición formal de gramáticas indexadas lineales [19] difiere de la anterior . [ aclaración necesaria ]
Los LIG (y sus equivalentes débiles ) son estrictamente menos expresivos (lo que significa que generan un subconjunto adecuado) que los lenguajes generados por otra familia de formalismo débilmente equivalente, que incluye: LCFRS , MCTAG , MCFG y gramáticas minimalistas (MG). La última familia puede (también) analizarse en tiempo polinomial . [20]
Gramáticas de índice distribuidas
Otra forma de gramáticas indexadas, introducida por Staudacher (1993), [12] es la clase de gramáticas de índice distribuido (DIG). Lo que distingue a las DIG de las Gramáticas indexadas de Aho es la propagación de índices. A diferencia de los IG de Aho, que distribuyen toda la pila de símbolos a todos los no terminales durante una operación de reescritura, los DIG dividen la pila en subestaciones y distribuyen las subestaciones a las no terminales seleccionadas.
El esquema de regla general para una regla de distribución binaria de DIG es la forma
- X [ f 1 ... f i f i +1 ... f n ] → α Y [f 1 ... f i ] β Z [ f i +1 ... f n ] γ
Donde α, β y γ son cadenas terminales arbitrarias. Para una cadena de distribución ternaria:
- X [ f 1 ... f i f i +1 ... f j f j +1 ... f n ] → α Y [f 1 ... f i ] β Z [ f i +1 ... f j ] γ W [ f j +1 ... f n ] η
Y así sucesivamente para un mayor número de no terminales en el lado derecho de la regla de reescritura. En general, si hay m no terminales en el lado derecho de una regla de reescritura, la pila se divide en m formas y se distribuye entre los nuevos no terminales. Tenga en cuenta que hay un caso especial en el que una partición está vacía, lo que efectivamente convierte a la regla en una regla LIG. Los lenguajes de índice distribuido son, por tanto, un superconjunto de los lenguajes de índice lineal.
Ver también
- Jerarquía de Chomsky
- Lenguaje indexado
Notas
- ^ "[" y "]" son meta símbolos para indicar la pila.
- ^ todos los demás no terminales reciben una pila vacía
- ^ a b Para generar cualquier cadena, algunas producciones deben admitirse sin símbolo no terminal en su lado derecho. Sin embargo, Gazdar no discutió este tema.
- ^ Cf. la gramática correctamente indexada para el mismo idioma dada anteriormente . La última regla, a saber. T [] → ε, de la gramática indexada lineal no se ajusta a la definición de Gazdar en un sentido estricto, cf. [nota 3]
Referencias
- ↑ a b Hopcroft, John E .; Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 978-0-201-02988-8.
- ^ Hopcroft y Ullman (1979), [1] Sección 14.3, p.389-390. Esta sección se omite en la segunda edición de 2003.
- ^ Aho, Alfred (1968). "Gramáticas indexadas: una extensión de las gramáticas libres de contexto". Revista de la ACM . 15 (4): 647–671. doi : 10.1145 / 321479.321488 .
- ^ a b Hayashi, Takeshi (1973). "En árboles de derivación de gramáticas indexadas: una extensión del teorema uvwxy" . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas . 9 : 61–92. doi : 10.2977 / prims / 1195192738 .
- ^ Hopcroft y Ullman (1979), [1] Notas bibliográficas, p.394-395
- ^ Alfred Aho (1969). "Autómatas de pila anidada". Revista de la ACM . 16 (3): 383–406. doi : 10.1145 / 321526.321529 .
- ^ Michael J. Fischer (1968). "Gramáticas con producciones tipo macro". Proc. 9th Ann. IEEE Symp. sobre la teoría de la conmutación y los autómatas (SWAT) . págs. 131-142. doi : 10.1109 / SWAT.1968.12 .
- ^ Sheila A. Greibach (1970). "Sustitución iterada anidada y AFL completa" . Información y control . 16 (1): 7–35. doi : 10.1016 / s0019-9958 (70) 80039-0 .
- ^ TSE Maibaum (1974). "Un enfoque generalizado de los lenguajes formales" . Revista de Ciencias de la Computación y Sistemas . 8 (3): 409–439. doi : 10.1016 / s0022-0000 (74) 80031-0 .
- ^ Robert H. Gilman (1996). "Un lema que se encoge para los lenguajes indexados". Informática Teórica . 163 (1–2): 277–281. arXiv : matemáticas / 9509205 . doi : 10.1016 / 0304-3975 (96) 00244-7 .
- ^ Robert H. Gilman (septiembre de 1995). "Un lema que se encoge para los lenguajes indexados". arXiv : matemáticas / 9509205 .
- ^ a b Staudacher, Peter (1993), Nuevas fronteras más allá del contexto libre: DI-gramáticas (DIG) y DI-autómatas. (PDF) , págs. 358–367, archivado desde el original (PDF) el 19 de julio de 2006 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ David J. Weir; Aravind K. Joshi (1988). "Gramáticas categóricas combinatorias: poder generativo y relación con los sistemas de reescritura libre de contexto lineal" (PDF) . Proc. 26º Encuentro Assoc. Computación. Ling . págs. 278-285.
- ↑ Según Staudacher (1993, p. 361 a la izquierda, sección 2.2), [12] el nombre "gramáticas indexadas lineales" no se usó en el artículo de 1988 de Gazdar, pero apareció más tarde, por ejemplo, en Weir y Joshi (1988). [13]
- ^ Gazdar, Gerald (1988). "Aplicabilidad de las gramáticas indexadas a los lenguajes naturales". En U. Reyle y C. Rohrer (ed.). Análisis del lenguaje natural y teorías lingüísticas . Estudios de lingüística y filosofía. 35 . D. Reidel Publishing Company. págs. 69–94. ISBN 978-1-55608-055-5.
- ^ Gazdar (1988), Apéndice, p.89
- ^ Gazdar 1988, Apéndice, p.89-91
- ^ Vijay-Shanker, K .; Weir, David J. 1994. (1994). "La equivalencia de cuatro extensiones de gramáticas libres de contexto" . Teoría de sistemas matemáticos . 27 (6): 511–546. doi : 10.1007 / bf01191624 .
- ^ p.517-518
- ^ Johan FAK van Benthem; Alice ter Meulen (2010). Manual de Lógica y Lenguaje (2ª ed.). Elsevier. pag. 404. ISBN 978-0-444-53727-0.
enlaces externos
- Capítulo "PNL en Prolog" sobre gramáticas e idiomas indexados