Gramática indexada

Las gramáticas indexadas son una generalización de gramáticas libres de contexto en que los símbolos no terminales están equipados con listas de banderas o símbolos de índice. El lenguaje producido por una gramática indexada se denomina lenguaje indexado.

Definición

Definición moderna por Hopcroft y Ullman

En publicaciones contemporáneas siguiendo a Hopcroft y Ullman (1979), ​ una gramática indexada se define formalmente como un 5-tuplo 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, una cadena ("pila") σ ∈ F * de símbolos de índice se adjunta a cada símbolo no terminal A ∈ N, denotado por A [σ]. Los símbolos terminales pueden no ser seguidos por pilas de índice. Para una pila de índices σ ∈ F * y una cadena α ∈ (N ∪ T) * de símbolos no terminales y terminales, α [σ] denota el resultado de unir [σ] 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 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 índice en las reglas de producción; entonces la regla de tipo 1, 2 y 3  se leen 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 asociada a cada símbolo no terminal. Cuando una producción como, por ejemplo, A [σ] → B [σ] C [σ] es aplicada, la pila de índice de A se copia a B y C. Además, una regla puede insertar un símbolo de índice en la pila o extraer su "máximo" (es decir, , más a la izquierda) símbolo de índice.

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 index de índice de la mano izquierda 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 φ insertando f en ella.
3. Si A [fσ] → α [σ] es una producción de tipo 3, entonces β A [fφ] γ ⇒ β α [φ] γ, utilizando de nuevo la definición de α [σ]. Es decir, el primer índice f se saca 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 lenguaje 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 por Aho

Históricamente, Alfred Aho (1968) introdujo la gramática indexada utilizando un formalismo diferente. Aho definió una gramática indexada como un 5-tuplo (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 ⊆ 2N × (N ∪ T) * es el conjunto finito de los llamados indicadores (cada indicador es en sí mismo un conjunto de las denominadas 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 → X1η1 ... Xkηk) de P coincide con una A ∈ N no terminal seguida de su cadena de banderas (posiblemente vacía) ζ ∈ F *. En contexto, γ Aζ δ, a través de p, deriva en γ X1θ1 ... Xkθk δ, donde θi = ηiζ si Xi fuera una palabra no terminal y la palabra vacía en caso contrario. Por lo tanto, las antiguas banderas de A se copian a cada nuevo no terminal producido por p. Cada producción puede ser simulada por producciones apropiadas de tipo 1 y 2 en el formalismo de Hopcroft / Ullman.
• Una producción de índice p = (A → X1 ... Xk) ∈ f coincide Afζ (la bandera f de la que procede 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 a γ X1θ1 ... Xkθk δ, donde θi es la palabra vacía cuando Xi es un terminal y ζ cuando es un no terminal. Cada producción de este tipo corresponde a una producción de tipo 3 en el formalismo de Hopcroft / Ullman.

Este formalismo es, por ejemplo utilizado por Hayashi (1973, p 65-66)..​

Ejemplos

En la práctica, montones 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 palabras triples {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 consiste en

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.

Se sabe que ambos lenguajes de ejemplo no están libres de contexto.

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.​

• Autómata de pila anidada unidireccional de Aho​
• Gramáticas macro de Fischer​
• Autómata con pila de pilas de Greibach​
• Caracterización algebraica de Maibaum​

Hayashi  generalizó el lema de bombeo a gramáticas indexadas. En cambio, Gilman.​​ da un "lema de contracción" para los idiomas indexados.

Gramáticas indexadas lineales

Gerald Gazdar ha definido una segunda clase, las gramáticas indexadas lineales (LIG), al requerir que se especifique como máximo recibir un no terminal en cada producción, 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 similar a una gramática indexada ordinaria, pero los requisitos de la 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 no terminales y terminales como α. Además, la relación de derivación directa ⇒ se define similar a la anterior. Esta nueva clase de gramáticas define una clase estrictamente más pequeña de idiomas, que pertenece a las clases levemente 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 {ww: w ∈ {a, b} *} y {$a^{n}b^{n}c^{n}$: n ≥ 1} son generables por una gramática indexada lineal.

Si se admiten las reglas de producción original y modificada, la clase de idioma sigue siendo los idiomas indexados.​

Ejemplo

Si dejamos σ denotar 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} 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.

Del mismo modo: 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 poderosos que los IGs. Una conversión de un LIG a un IG es relativamente simple. Las reglas LIG en general se ven aproximadamente como $X[\sigma ]\rightarrow \alpha Y[\sigma ]\beta$ ,módulo de la parte push / pop de una regla de reescritura. Los símbolos $\alpha$ y $\beta$ 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 es, por supuesto, en contra de cómo se definen los IGs: en un IG, los no terminales cuyas pilas no se empujan o se sacan deben tener exactamente la misma pila que el no terminal reescrito. Por lo tanto, de alguna manera, necesitamos tener no terminales en $\alpha$ y $\beta$ que, a pesar de tener pilas no vacías, se comporten como si tuvieran pilas vacías

Consideremos la regla $X[\sigma ]\rightarrow Y[]Z[\sigma f]$ como ejemplo de caso. Al convertir esto en un IG, el reemplazo de  $Y[]$ debe ser algo como  $Y'[\sigma ]$ que se comporte exactamente como  $Y[]$ independientemente de lo que sea $\sigma$ . Para lograr esto, podemos simplemente tener un par de reglas que tome cualquier  $Y'[\sigma ]$ donde  $\sigma$ no esté vacío, y muestre símbolos de la pila. Entonces, cuando la pila está vacía, se puede volver a escribir como $Y[]$ .

$Y'[\sigma ]\rightarrow Y'[\sigma ]$

$Y'[]\rightarrow Y[]$

Podemos aplicar esto en general para derivar un IG de un LIG. Entonces, por ejemplo, si el LIG para el lenguaje { ${a^{n}b^{n}c^{n}d^{m}|n>=1,m>=1}$} es el siguiente:

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

$S[\sigma ]\to T[\sigma ]V[]$

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

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

La regla sentencial aquí no es una regla IG, pero usando el algoritmo de conversión anterior, podemos definir nuevas reglas para $V'$ cambiando la gramática a:

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

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

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

$V[]\to d~|~dV[]$

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

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

Cada regla ahora se ajusta a la definición de IG, en la que todos los no terminales en el lado derecho de una regla de reescritura reciben una copia de la pila del símbolo reescrito. Las gramáticas indexadas son capaces de describir todos los lenguajes que las gramáticas indexadas linealmente pueden describir.

Relación con otro formalismo

Vijay-Shanker y Weir (1994) demuestran que las gramáticas indexadas lineales, las gramáticas categoriales combinatorias, las gramáticas de adyacencia de árbol y las gramáticas principales definen la misma clase de lenguajes de cuerdas. Su definición formal de gramáticas indexadas lineales difiere de la anterior.

Los LIG (y sus equivalentes débiles) son estrictamente menos expresivos (lo que significa que generan un subconjunto propio) 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) ser analizada en tiempo polinomial.

Gramáticas indexadas distribuidas

Otra forma de gramáticas indexadas, introducida por Staudacher (1993), 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 IGs de Aho, que distribuyen la pila de símbolos completa a todos los no terminales durante una operación de reescritura, los DIG dividen la pila en subbases y distribuyen las subbases a no terminales seleccionados.

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

X[f₁...f_if_i+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_n] γ

Donde α, β y γ son cadenas terminales arbitrarias. Para una cadena ternariamente distribuida:

X[f₁...f_if_i+1...f_jf_j+1...f_n] → α Y[f₁...f_i] β Z[f_i+1...f_j] γ W[f_j+1...f_n] η

Y así sucesivamente para números más altos 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 dos maneras y se distribuye entre las nuevas no terminales. Tenga en cuenta que hay un caso especial en el que una partición está vacía, lo que hace que la regla sea una regla LIG. Los lenguajes del Índice Distribuido son, por lo tanto, un superconjunto de los idiomas de Índice Lineal.

Véase también

• Jerarquía de Chomsky
• Lenguaje indexado

Enlaces externos

• "NLP in Prolog" chapter on indexed grammars and languages

• Datos: Q6590011