Gramática indexada

Las gramáticas indexadas son una generalización de las gramáticas libres de contexto en el sentido de 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 llama 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 tupla de 5 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 inicial , 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 terminales no pueden ir seguidos de pilas de índices. Para una pila de índice σ ∈ F ^* y una cadena α ∈ ( N ∪ T ) ^* de símbolos terminales y no 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

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 terminales y no 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 se lee entonces 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 índice adjunta a cada símbolo no terminal. Cuando se aplica una producción como, por ejemplo, A [ σ ] → B [ σ ] C [ σ ] , la pila de índice 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 aparecer 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:

1. Si A [ σ ] → α [ σ ] es una producción de tipo 1, entonces β A [ φ ] γ ⇒ β α [ φ ] γ , usando la definición anterior. Es decir, la pila de índice φ 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 índice del lado derecho se obtiene de la pila φ del lado izquierdo empujando f sobre ella.
3. 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 es habitual, la relación de derivación∗⇒se define como la clausura transitiva reflexiva 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 tupla de 5 ( 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 índices )
4. P ⊆ N × ( NF ^* ∪ T ) ^* es el conjunto finito de producciones
5. S ∈ N es el símbolo inicial

Las derivaciones directas fueron las siguientes:

• Una producción p = ( A → X ₁ η ₁ … X _k η _k ) de P coincide con un no terminal A ∈ N seguido de su cadena (posiblemente vacía) de banderas ζ ∈ F ^* . En contexto, γ Aζ δ , a través de p , deriva a γ X ₁ θ ₁ … X _k θ _k δ , donde θ _i = η _i ζ si X _i fuera un no terminal y la palabra vacía en caso contrario. Por lo tanto , las antiguas banderas de A se copian en cada nuevo no terminal producido por p . Cada una de estas producciones puede simularse 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 de la que proviene f debe coincidir con el primer símbolo que sigue al no terminal A ) y copia la cadena de índice restante ζ en cada nuevo no terminal: γ Afζ δ deriva a γ X ₁ θ ₁ … X _k θ _k δ , donde θ _i es la palabra vacía cuando X _i es terminal y ζ cuando es no terminal. Cada una de estas producciones corresponde a una producción de tipo 3 en el formalismo de Hopcroft/Ullman.

Este formalismo lo utiliza, por ejemplo, Hayashi (1973, p. 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 contextual de triples 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 abad .

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 consta de

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 anidados unidireccionales de Aho ^[6]
• 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 gramáticas indexadas. Por el contrario, Gilman ^{[10] [11]} ofrece un "lema reductor" para lenguajes indexados.

Gramáticas indexadas lineales

Gerald Gazdar ha definido una segunda clase, las gramáticas indexadas lineales ( LIG ), ^[14] al requerir que como máximo un no terminal en cada producción se especifique 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 usan como arriba, y β ∈ ( N ∪ T ) ^* es una cadena de símbolos terminales y no 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 ligeramente sensibles al contexto .

El lenguaje { www  : w ∈ { a , b } ^* } es generable mediante una gramática indexada, pero no mediante una gramática indexada lineal, mientras que tanto { ww  : w ∈ { a , b } ^* } como { a ⁿ b ⁿ c ⁿ  : n ≥ 1 } son generables mediante una gramática indexada lineal.

Si se admiten tanto las reglas de producción originales como las modificadas, la clase de idioma seguirá siendo el idioma indexado. ^[dieciséis]

Ejemplo

Si σ denota una secuencia arbitraria de símbolos de pila, podemos definir una gramática para el lenguaje L = { a ⁿ b ⁿ c ⁿ | norte ≥ 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

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 poderosos que los IG. Una conversión de LIG a IG es relativamente sencilla. ^[17] Las reglas LIG en general se parecen aproximadamente a , 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, según la definición de un LIG. Esto, por supuesto, va en contra de cómo se definen los IG: en un IG, los no terminales cuyas pilas no se empujan ni se extraen deben tener exactamente la misma pila que el no terminal reescrito. Por lo tanto, de alguna manera, necesitamos tener no terminales que , a pesar de tener pilas no vacías, se comporten como si las tuvieran. ${\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

Consideremos la regla como un caso de ejemplo. Al convertir esto en un IG, el reemplazo debe ser uno que se comporte exactamente igual, independientemente de lo que sea. Para lograr esto, simplemente podemos tener un par de reglas que tomen cualquier lugar que 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. Entonces, por ejemplo, si el LIG para el idioma 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 de oración aquí no es una regla de IG, pero usando 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 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] demuestran que las gramáticas indexadas lineales, las gramáticas categoriales combinatorias , las gramáticas contiguas a árboles y las gramáticas principales definen la misma clase de lenguajes de cadenas. Su definición formal de gramáticas indexadas lineales ^[19] difiere de la anterior. ^{[ se necesita aclaración ]}

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). Esta última familia (también) se puede analizar en tiempo polinomial . ^[20]

Gramáticas de índice distribuido

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 los 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 subpilas y distribuyen las 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 de 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 divide 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. Los lenguajes de índice distribuido son, por lo tanto, un superconjunto de los lenguajes de índice lineal.

Ver también

• Jerarquía chomsky

Notas

1. "[" y "]" son metasímbolos para indicar la pila.
2. todos los demás no terminales reciben una pila vacía
3. Para generar cualquier cadena, se debe admitir que algunas producciones no tienen ningún símbolo no terminal en su lado derecho. Sin embargo, Gazdar no habló de este tema.
4. Cfr. la gramática correctamente indexada para el mismo idioma proporcionada anteriormente. La última regla, a saber. T []→ε, de la gramática indexada lineal no se ajusta a la definición de Gazdar en sentido estricto, cf. ^{[nota 3]}

Referencias

1. Hopcroft, John E .; Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de autómatas . Addison-Wesley. ISBN 978-0-201-02988-8.
2. Hopcroft y Ullman (1979), ^[1] Sección 14.3, páginas 389-390. Esta sección se omite en la segunda edición de 2003.
3. Ah, 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 Investigaciones en Ciencias Matemáticas . 9 : 61–92. doi : 10.2977/prims/1195192738 .
5. Hopcroft y Ullman (1979), ^[1] Notas bibliográficas, páginas 394-395
6. Alfred Aho (1969). "Autómatas de pila anidados". Revista de la ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID  685569.
7. Michael J. Fischer (1968). "Gramáticas con producciones tipo macro". Proc. 9no ann. Síntoma IEEE. sobre Teoría de Conmutación y Autómatas (SWAT) . págs. 131-142. doi :10.1109/SWAT.1968.12.
8. Sheila A. Greibach (1970). "AFL completo y sustitución iterada anidada". Información y Control . 16 (1): 7–35. doi : 10.1016/s0019-9958(70)80039-0 .
9. EET Maibaum (1974). "Un enfoque generalizado de los lenguajes formales". Revista de Ciencias de la Computación y de Sistemas . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .
10. Robert H. Gilman (1996). "Un lema cada vez más reducido 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. S2CID  14479068.
11. Robert H. Gilman (septiembre de 1995). "Un lema cada vez más reducido para los lenguajes indexados". arXiv : matemáticas/9509205 .
12. Staudacher, Peter (1993), "Nuevas fronteras más allá de la ausencia 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.
13. David J. Weir; Aravind K. Joshi (1988). "Gramáticas categoriales combinatorias: poder generativo y relación con sistemas de reescritura lineales libres de contexto" (PDF) . Proc. 26ª Reunión Asoc. Computadora. Ling . págs. 278–285.
14. Según Staudacher (1993, p.361 izquierda, Sección 2.2), ^[12] el nombre "gramáticas indexadas lineales" no se usó en el artículo de Gazdar de 1988, pero apareció más tarde, por ejemplo, en Weir y Joshi (1988). ^[13]
15. Gazdar, Gerald (1988). "Aplicabilidad de gramáticas indexadas a 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. vol. 35. Compañía editorial D. Reidel. págs. 69–94. ISBN 978-1-55608-055-5.
16. Gazdar (1988), Apéndice, p.89
17. Gazdar 1988, Apéndice, páginas 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áginas 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