Gramática indexada

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 indicadores o símbolos de índice . El lenguaje producido por una gramática indexada se denomina lenguaje indexado .

Definición

Definición moderna de Hopcroft y Ullman

En publicaciones contemporáneas posteriores a Hopcroft y Ullman (1979), ^[2] una gramática indexada se define formalmente como una 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 .

En producciones así como en derivaciones de gramáticas indexadas, una cadena ("pila") σ ∈ F * de símbolos de índice se adjunta a cada símbolo no terminal A ∈ N , denotado por A [ σ ]. ^{[nota 1]} Los símbolos terminales no pueden ser seguidos por pilas de índice. Para una pila de índice σ ∈ 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 un B C d E con un terminal a , d ∈ T y B , C , E ∈ N símbolos no terminales, entonces α [ σ ] denota un B [ σ ] C [ σ ] d E [ σ ]. Usando esta notación, cada producción en P tiene que ser de la forma

1. A [σ] → α[σ],
2. A [σ] → B [ f σ], o
3. 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 entonces se lee 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 se aplica una producción como, por ejemplo, A [ σ ] → B [ σ ] C [ σ ], la pila de índices de A se copia tanto en B como en C. Además, una regla puede insertar un símbolo de índice en la pila o hacer que su símbolo de índice "superior" (es decir, el más a la izquierda) aparezca.

Formalmente, la relación ⇒ ("derivación directa") se define en el conjunto ( N [ F ^* ]∪ T ) ^* de "formas oracionales" de la siguiente manera:

1. Si A [ σ ] → α [ σ ] es una producción de tipo 1, entonces β A [ φ ] γ ⇒ β α [ φ ] γ , utilizando 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.
2. 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 al insertar f sobre ella.
3. Si A [ fσ ] → α [ σ ] es una producción de tipo 3, entonces β A [ fφ ] γ ⇒ β α [ φ ] γ , utilizando 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 es habitual, la relación de derivación∗⇒se define como el cierre transitivo reflexivo de la derivación directa ⇒. El lenguaje L ( G ) = { w ∈ T ^* : S ∗⇒ w } es el conjunto de todas las cadenas de símbolos terminales derivables del símbolo inicial.

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 5-tupla ( N , T , F , P , S ) donde

1. N es un alfabeto finito de variables o símbolos no terminales
2. T es un alfabeto finito de símbolos terminales
3. F ⊆ 2 ^{N × ( N ∪ T ) *} es el conjunto finito de las llamadas banderas (cada bandera es en sí misma un conjunto de las llamadas producciones de índice )
4. P ⊆ N × ( NF ^* ∪ T ) ^* es el conjunto finito de producciones
5. S ∈ N es el símbolo de inicio

Las derivaciones directas fueron las siguientes:

• Una producción p = ( A → X ₁ η ₁ … X _k η _k ) a partir de P coincide con un no terminal A ∈ N seguido de su cadena (posiblemente vacía) de indicadores ζ ∈ F ^* . En contexto, γ Aζ δ , a través de p , deriva a γ X ₁ θ ₁ … 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 de Hopcroft/Ullman.
• Una producción de índice p = ( A → X ₁ … 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 en γ X ₁ θ ₁ … 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ágs. 65-66). ^[4]

Ejemplos

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 tripletas de palabras { www  : w ∈ { a , b } ^* }:

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 ⁿ b ⁿ c ⁿ : n ≥ 1 }, donde el conjunto de producción P consiste en

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 según 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 anidada unidireccional de Aho ^[6]
• Las macrogramá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 las gramáticas indexadas. Por el contrario, Gilman ^{[10] [11]} ofrece un "lema de contracción" para los lenguajes indexados.

Gramáticas lineales indexadas

Gerald Gazdar ha definido una segunda clase, las gramáticas indexadas lineales ( LIG ), ^[14] al requerir que, como máximo, se especifique un no terminal en cada producción como receptor de la pila, ^{[nota 2]} mientras que en una gramática indexada ordinaria, 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:

1. A [ σ ] → α [] B [ σ ] β [],
2. A [ σ ] → α [] B [ fσ ] β [],
3. A [ fσ ] → α [] B [ σ ] β [],

donde A , B , f , σ , α se utilizan como antes, 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 forma similar a la anterior. Esta nueva clase de gramáticas define una clase estrictamente más pequeña de lenguajes, ^[15] que pertenece a las clases ligeramente sensibles al contexto .

El lenguaje { www  : w ∈ { a , b } ^* } es generable por una gramática indexada, pero no por una gramática indexada lineal, mientras que tanto { ww  : w ∈ { a , b } ^* } como { a ⁿ b ⁿ c ⁿ  : 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 la de los idiomas indexados. ^[16]

Ejemplo

Si σ denota una secuencia arbitraria de símbolos de pila, podemos definir una gramática para el lenguaje L = { a ⁿ b ⁿ c ⁿ | n ≥ 1 } ^{[nota 4]} como

Para derivar la cadena abc tenemos los pasos:

S [] ⇒ aS [ f ] c ⇒ aT [ f ] c ⇒ aT [] bc ⇒ abc

Similarmente:

S [ ] ⇒ aS [ f ] c ⇒ aaS [ ff ] cc ⇒ aaT [ ff ] cc ⇒ aaT [ f ] bcc ⇒ aaT [ ] bbcc ⇒ aabbcc

Poder computacional

Los lenguajes indexados linealmente son un subconjunto de los lenguajes indexados, y por lo tanto todos los LIG pueden ser recodificados como IG, haciendo que los LIG sean estrictamente menos poderosos que los IG. Una conversión de un LIG a un IG es relativamente simple. ^[17] Las reglas LIG en general se ven aproximadamente como , módulo la parte push/pop de una regla de reescritura. Los símbolos 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, por la definición de un 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 de las que no se está 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 comporten como si tuvieran pilas vacías. ${\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

Considere la regla como un caso de ejemplo. Al convertir esto en un IG, el reemplazo de debe ser algo que se comporte exactamente como independientemente de lo que sea. Para lograr esto, simplemente podemos tener un par de reglas que tomen cualquier donde no esté vacío y extraigan símbolos de la pila. Luego, cuando la pila esté vacía, se puede reescribir como . ${\displaystyle X[\sigma ]\to Y[]Z[\sigma f]}$ ${\displaystyle Y[]}$ ${\displaystyle Y^{\prime }[\sigma ]}$ ${\displaystyle Y[]}$ ${\displaystyle \sigma }$ ${\displaystyle Y^{\prime }[\sigma ]}$ ${\displaystyle \sigma }$ ${\displaystyle Y[]}$

${\displaystyle Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]}$

${\displaystyle Y^{\prime }[]\to Y[]}$

Podemos aplicar esto en general para derivar un IG a partir de un LIG. Por ejemplo, si el LIG para el lenguaje es el siguiente: ${\displaystyle \{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}}$

${\displaystyle S[\sigma ]\to T[\sigma ]V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

La regla oracional aquí no es una regla IG, pero al usar el algoritmo de conversión anterior, podemos definir nuevas reglas para , cambiando la gramática a: ${\displaystyle V^{\prime }}$

${\displaystyle S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[]\to V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

Cada regla se ajusta ahora 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 lo tanto, las gramáticas indexadas pueden describir todos los idiomas que las gramáticas indexadas linealmente pueden describir.

Relación con otros formalismos

Vijay-Shanker y Weir (1994) ^[18] demuestran que las gramáticas lineales indexadas, las gramáticas categóricas combinatorias , las gramáticas de contigüidad de árboles y las gramáticas de núcleo definen la misma clase de lenguajes de cadenas. Su definición formal de gramáticas lineales indexadas ^[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 incluyen: LCFRS , MCTAG, MCFG y gramáticas minimalistas (MG). La última familia puede (también) analizarse en tiempo polinomial . ^[20]

Gramáticas de índices distribuidos

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 las IG de Aho, que distribuyen toda la pila de símbolos a todos los no terminales durante una operación de reescritura, las DIG dividen la pila en subpilas y distribuyen estas subpilas a los no terminales seleccionados.

El esquema de regla general para una regla de distribución binaria de DIG es la forma

X [ f ₁ ... f _i f _{i +1} ... f _n ] → α Y [ f ₁ ... f _i ] β Z [ f _{i +1} ... f _n ] γ

Donde α, β y γ son cadenas terminales arbitrarias. Para una cadena con distribución ternaria:

X [ f ₁ ... f _i f _{i +1} ... f _j f _{j +1} ... f _n ] → α Y [ f ₁ ... 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 particiona de m maneras y se distribuye entre los nuevos no terminales. Observe 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. Por lo tanto, los lenguajes de índice distribuido son un superconjunto de los lenguajes de índice lineal.

Véase también

• Jerarquía de Chomsky

Notas

1. "[" y "]" son símbolos meta para indicar la pila.
2. todos los demás no terminales reciben una pila vacía
3. Para generar cualquier cadena, se deben admitir algunas producciones que no tengan ningún símbolo no terminal en su lado derecho. Sin embargo, Gazdar no discutió este tema.
4. Véase la gramática indexada correctamente para el mismo idioma que se da más arriba. La última regla, es decir, T []→ε, de la gramática indexada lineal no se ajusta a la definición de Gazdar en un sentido estricto, véase ^{[nota 3]}

Referencias

1. Hopcroft, John E. ; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 978-0-201-02988-8.
2. Hopcroft y Ullman (1979), ^[1] Sect.14.3, p.389-390. Esta sección se omite en la segunda edición de 2003.
3. 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 . S2CID  9539666.
4. Hayashi, Takeshi (1973). "Sobre árboles de derivación de gramáticas indexadas: una extensión del teorema uvwxy". Publicaciones del Instituto de Investigación de Ciencias Matemáticas . 9 : 61–92. doi : 10.2977/prims/1195192738 .
5. Hopcroft y Ullman (1979), ^[1] Notas bibliográficas, p.394-395
6. Alfred Aho (1969). "Autómatas de pila anidada". Revista de la ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID  685569.
7. Michael J. Fischer (1968). "Gramáticas con producciones similares a macro". Proc. 9.° Simposio anual IEEE sobre conmutación y teoría de autómatas (SWAT) . págs. 131-142. doi :10.1109/SWAT.1968.12.
8. Sheila A. Greibach (1970). "AFL completos y sustitución iterada anidada". Información y control . 16 (1): 7–35. doi : 10.1016/s0019-9958(70)80039-0 .
9. TSE Maibaum (1974). "Un enfoque generalizado de los lenguajes formales". Revista de informática y ciencias de sistemas . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .
10. Robert H. Gilman (1996). "Un lema de contracción para lenguajes indexados". Ciencias de la computación teórica . 163 (1–2): 277–281. arXiv : math/9509205 . doi :10.1016/0304-3975(96)00244-7. S2CID  14479068.
11. Robert H. Gilman (septiembre de 1995). "Un lema decreciente para lenguajes indexados". arXiv : math/9509205 .
12. Staudacher, Peter (1993), "Nuevas fronteras más allá de la libertad de contexto: gramáticas DI (DIG) y autómatas DI". (PDF) , Sexta Conferencia del Capítulo Europeo de la Asociación de Lingüística Computacional (EACL '93) , págs. 358–367
13. David J. Weir; Aravind K. Joshi (1988). "Gramáticas categóricas combinatorias: poder generativo y relación con los sistemas de reescritura lineales libres de contexto" (PDF) . Actas de la 26.ª reunión de la Asociación de Computación Ling . págs. 278–285.
14. Según Staudacher (1993, p.361 izquierda, Sect.2.2), ^[12] el nombre "gramáticas indexadas lineales" no se utilizó en el artículo de Gazdar de 1988, sino que apareció más tarde, por ejemplo en Weir y Joshi (1988). ^[13]
15. Gazdar, Gerald (1988). "Aplicabilidad de las gramáticas indexadas a las lenguas naturales". En U. Reyle y C. Rohrer (ed.). Análisis sintáctico de lenguas naturales y teorías lingüísticas . Estudios de lingüística y filosofía. Vol. 35. D. Reidel Publishing Company. págs. 69–94. ISBN 978-1-55608-055-5.
16. Gazdar (1988), Apéndice, pág. 89
17. Gazdar 1988, Apéndice, págs. 89-91
18. 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. S2CID  12336597.{{cite journal}}: CS1 maint: numeric names: authors list (link)
19. págs. 517-518
20. 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 y lenguajes indexados