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
[editar]Definición moderna por Hopcroft y Ullman
[editar]En publicaciones contemporáneas siguiendo a Hopcroft y Ullman (1979), [2] 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")
- A[
σ ] →α [σ ], - A[
σ ] → B[fσ ], o - A[f
σ ] →α [σ ],
donde A, B ∈ N son símbolos no terminales, f ∈ F es un índice,
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 [
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 [φ ]γ ⇒β α [φ ]γ , 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. - 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. - 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
[editar]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
- N es un alfabeto finito de variables o símbolos no terminales
- T Es un alfabeto finito de símbolos terminales
- 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)
- 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 → 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)..[3]
Ejemplos
[editar]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 {: n ≥ 1}, donde el conjunto de producción P consiste en
S[ σ ] → T[gσ ]A[f σ ] → a A[σ ]A[g σ ] → aT[ σ ] → T[fσ ]B[f σ ] → b B[σ ]B[g σ ] → bT[ σ ] → 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
[editar]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.[4]
- Autómata de pila anidada unidireccional de Aho[5]
- Gramáticas macro de Fischer[6]
- Autómata con pila de pilas de Greibach[7]
- Caracterización algebraica de Maibaum[4]
Hayashi generalizó el lema de bombeo a gramáticas indexadas. En cambio, Gilman.[8][9] da un "lema de contracción" para los idiomas indexados.
Gramáticas indexadas lineales
[editar]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:
- A[
σ ] →α [] B[σ ]β [], - A[
σ ] →α [] B[fσ ]β [], - A[f
σ ] →α [] B[σ ]β [],
donde A, B, f,
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 {: 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.[10]
Ejemplo
[editar]Si dejamos
S[ σ ]→ a S[f σ ] cS[ σ ]→ T[ σ ]T[f σ ]→ T[ σ ] bT[] → ε
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
[editar]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 ,módulo de 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 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 y que, a pesar de tener pilas no vacías, se comporten como si tuvieran pilas vacías
Consideremos la regla como ejemplo de caso. Al convertir esto en un IG, el reemplazo de debe ser algo como que se comporte exactamente como independientemente de lo que sea . Para lograr esto, podemos simplemente tener un par de reglas que tome cualquier donde no esté vacío, y muestre símbolos de la pila. Entonces, cuando la pila está vacía, se puede volver a escribir como .
Podemos aplicar esto en general para derivar un IG de un LIG. Entonces, por ejemplo, si el LIG para el lenguaje { } es el siguiente:
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 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
[editar]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
[editar]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[f1...fifi+1...fn] →
α Y[f1...fi]β Z[fi+1...fn]γ
Donde
- X[f1...fifi+1...fjfj+1...fn] →
α Y[f1...fi]β Z[fi+1...fj]γ W[fj+1...fn]η
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
[editar]Notas
[editar]Referencias
[editar]- ↑ Hopcroft, John E.; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
- ↑ Hopcroft and Ullman (1979),[1] Sect.14.3, p.389-390. This section is omitted in the 2nd edition 2003.
- ↑ T. Hayashi (1973). «On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem». Publication of the Research Institute for Mathematical Sciences (Research Institute for Mathematical Sciences) 9 (1): 61-92. doi:10.2977/prims/1195192738.
- ↑ a b T.S.E. Maibaum (1974). «A Generalized Approach to Formal Languages». J. Computer and System Sciences 8 (3): 409-439. doi:10.1016/s0022-0000(74)80031-0.
- ↑ Alfred Aho (1969). «Nested Stack Automata». Journal of the ACM 16 (3): 383-406. doi:10.1145/321526.321529.
- ↑ Michael J. Fischer (1968). «Grammars with Macro-Like Productions». Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131-142.
- ↑ Sheila A. Greibach (1970). «Full AFL's and Nested Iterated Substitution». Information and Control 16 (1): 7-35. doi:10.1016/s0019-9958(70)80039-0.
- ↑ Robert H. Gilman (1996). «A Shrinking Lemma for Indexed Languages». Theoretical Computer Science 163: 277-281. doi:10.1016/0304-3975(96)00244-7.
- ↑ Robert H. Gilman (Sep 1995). A Shrinking Lemma for Indexed Languages.
- ↑ Gazdar (1988), Appendix, p.89