Hispanopedia Wiki
Articulo de referencia

gramática indexada

Las gramáticas indexadas son una generalización de las gramáticas libres de contexto, ya que los no terminales están equipados con listas de indicadores o símbolos de índice . E...

Hispanopedia WikiContenido en espanolLectura gratuita

Las gramáticas indexadas son una generalización de las gramáticas libres de contexto, ya 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 que siguen a Hopcroft y Ullman (1979), [ 2 ] una gramática indexada se define formalmente como una 5-tupla G = ⟨ N , T , F , P , S ⟩ donde

En producciones y derivaciones de gramáticas indexadas, una cadena ("pila") σ ∈ F * de símbolos de índice se adjunta a cada símbolo no terminal A ∈ N , denotada por A [ σ ]. [ nota 1 ] Los símbolos terminales no pueden ir seguidos de 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 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 [ σ ]. Utilizando 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 a B como a C. Además, una regla puede insertar un símbolo de índice en la pila o extraer su símbolo de índice "superior" (es decir, el más a la izquierda).

Formalmente, la relación ⇒ ("derivación directa") se define en el conjunto ( N [ F * ]∪ T ) * de "formas sentenciales" 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 índices φ del lado izquierdo de la regla se copia a 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φ ] γ ⇒ β α [ φ ] γ , 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 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 í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 1 η 1 ... 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 , se deriva en γ 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, las banderas antiguas de A se copian a 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 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ζ δ se deriva en γ 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 de Hopcroft/Ullman.

Este formalismo es utilizado, por ejemplo, por 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 las ternas de palabras { www  : w ∈ { a , b } * }:

Una derivación de abbababbabb 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

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 .

Ninguno de los dos lenguajes de ejemplo es libre 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 ].

Hayashi [ 4 ] generalizó el lema de bombeo a gramáticas indexadas. Por el contrario, Gilman [ 10 ] [ 11 ] da un "lema de contracción" 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 forma similar a una gramática indexada ordinaria, pero los requisitos de forma de la producción se modifican a:

  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 no terminales y terminales como α . [ nota 3 ] Además, la relación de derivación directa ⇒ se define de forma similar a arriba. 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 por una gramática indexada, pero no por una gramática indexada lineal, mientras que tanto { ww  : w ∈ { a , b } * } como { 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 lenguaje sigue siendo la de los lenguajes indexados. [ 16 ]

Ejemplo

Si denotamos por σ una secuencia 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

Para obtener la cadena "abc" tenemos los siguientes 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 se pueden recodificar como IG, lo que hace que los LIG sean estrictamente menos potentes que los IG. Una conversión de un LIG a un IG es relativamente simple. [ 17 ] Las reglas LIG en general se ven aproximadamente comoincógnita[σ]→αY[σ]β{\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }, módulo la parte push/pop de una regla de reescritura. Los símbolosα{\displaystyle \alpha }yβ{\displaystyle \beta }representan cadenas de símbolos terminales y/o no terminales, y cualquier símbolo no terminal en cualquiera de ellas debe tener una pila vacía, por definición de un LIG. Esto es, por supuesto, contrario a cómo se definen los IG: en un IG, los no terminales cuyas pilas no se insertan ni se extraen deben tener exactamente la misma pila que el no terminal reescrito. Por lo tanto, de alguna manera, necesitamos tener no terminales enα{\displaystyle \alpha }yβ{\displaystyle \beta }que, a pesar de tener pilas no vacías, se comportan como si tuvieran pilas vacías.

Considere la reglaincógnita[σ]→Y[]Z[σF]{\displaystyle X[\sigma ]\to Y[]Z[\sigma f]}como caso de ejemplo. Al convertir esto a un IG, el reemplazo deY[]{\displaystyle Y[]}debe haber algunoY′[σ]{\displaystyle Y^{\prime }[\sigma ]}que se comporta exactamente comoY[]{\displaystyle Y[]}independientemente de lo queσ{\displaystyle \sigma }es. Para lograr esto, podemos simplemente tener un par de reglas que tomen cualquierY′[σ]{\displaystyle Y^{\prime }[\sigma ]}dóndeσ{\displaystyle \sigma }no está vacía y extrae símbolos de la pila. Luego, cuando la pila está vacía, se puede reescribir comoY[]{\displaystyle Y[]}.

Y′[σF]→Y′[σ]{\displaystyle Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]}
Y′[]→Y[]{\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 idioma{anortebnortedonortedmetro|norte≥1,metro≥1}{\displaystyle \{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}}es el siguiente:

S[σ]→T[σ]V[]{\displaystyle S[\sigma ]\to T[\sigma ]V[]}
V[]→d | dV[]{\displaystyle V[]\to d~|~dV[]}
T[σ]→aT[σF]do | U[σ]{\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}
U[σF]→bU[σ]{\displaystyle U[\sigma f]\to bU[\sigma ]}
U[]→ϵ{\displaystyle U[]\to \epsilon }

La regla sentencial aquí no es una regla IG, pero usando el algoritmo de conversión anterior, podemos definir nuevas reglas paraV′{\displaystyle V^{\prime }}, cambiando la gramática a:

S[σ]→T[σ]V′[σ]{\displaystyle S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]}
V′[σF]→V′[σ]{\displaystyle V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]}
V′[]→V[]{\displaystyle V^{\prime }[]\to V[]}
V[]→d | dV[]{\displaystyle V[]\to d~|~dV[]}
T[σ]→aT[σF]do | U[σ]{\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}
U[σF]→bU[σ]{\displaystyle U[\sigma f]\to bU[\sigma ]}
U[]→ϵ{\displaystyle U[]\to \epsilon }

Ahora, cada regla se ajusta a la definición de una gramática indexada (GI), en la que todos los no terminales del 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 lenguajes que pueden describir las gramáticas indexadas linealmente.

Relación con otros formalismos

Vijay-Shanker y Weir (1994) [ 18 ] demuestran que las gramáticas indexadas lineales, las gramáticas categóricas combinatorias , las gramáticas de adjunción de árboles y las gramáticas de cabeza definen la misma clase de lenguajes de cadenas. Su definición formal de gramáticas indexadas lineales [ 19 ] difiere de la anterior .

Las LIG (y sus equivalentes débiles ) son estrictamente menos expresivas (es decir, generan un subconjunto propio) que los lenguajes generados por otra familia de formalismos débilmente equivalentes, que incluyen: LCFRS , MCTAG , MCFG y gramáticas minimalistas (MG). Esta última familia también puede analizarse 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 las DIG de las gramáticas indexadas de Aho es la propagación de los í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 las subpilas a no terminales seleccionados.

El esquema de reglas generales 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 ternariamente distributiva:

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 partes y se distribuye entre los nuevos no terminales. Cabe destacar que existe un caso especial en el que una partición está vacía, lo que convierte 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

Notas

  1. ↑ "[" y "]" son meta símbolos para indicar la pila.
  2. ↑ Todos los demás no terminales reciben una pila vacía
  3. 1 2 Para generar cualquier cadena, algunas producciones deben ser admitidas sin tener un símbolo no terminal en su lado derecho. Sin embargo, Gazdar no abordó este tema.
  4. ↑ Cf. la gramática indexada correctamente para el mismo lenguaje dada 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. 1 2 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 2.ª edición de 2003.
  3. ↑ Aho, Alfred (1968). "Gramáticas indexadas: una extensión de las gramáticas libres de contexto" . Journal of the ACM . 15 (4): 647– 671. doi : 10.1145/321479.321488 . S2CID 9539666 . 
  4. 1 2 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ágs. 394-395
  6. ↑ Alfred Aho (1969). "Autómatas de pila anidados" . Journal of the ACM . 16 (3): 383– 406. doi : 10.1145/321526.321529 . S2CID 685569 . 
  7. ↑ Michael J. Fischer (1968). "Gramáticas con producciones similares a macros". Actas del 9.º Simposio Anual del IEEE sobre Teoría de la Conmutación y los 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" . Journal of Computer and System Sciences . 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". Theoretical Computer Science . 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 de reducción para lenguajes indexados". arXiv : math/9509205 .
  12. 1 2 Staudacher, Peter (1993), "Nuevas fronteras más allá de la ausencia de contexto: DI-gramáticas (DIG) y DI-autómatas." (PDF) , Sexta Conferencia del Capítulo Europeo de la Asociación de Lingüística Computacional (EACL '93) , pp. 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 Lingüística Computacional. págs. 278–285 . 
  14. ↑ Según Staudacher (1993, p. 361 izquierda, Sect. 2.2), [ 12 ] el nombre "gramáticas indexadas lineales" no se usó 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 los lenguajes naturales». En U. Reyle y C. Rohrer (eds.). Análisis sintáctico del lenguaje natural y teorías lingüísticas . Estudios en lingüística y filosofía. Vol. 35. D. Reidel Publishing Company. pp. 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" . Mathematical Systems Theory . 27 (6): 511– 546. doi : 10.1007/bf01191624 . S2CID 12336597 . {{cite journal}}: CS1 maint: nombres numéricos: lista de autores ( enlace )
  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.
  • Capítulo de "PNL en Prolog" sobre gramáticas indexadas y lenguajes