# Gramàtica indexada

Les gramàtiques indexades son una generalització de les gramàtiques lliures del context en les que els símbols no terminals estan equipats amb una llista d'etiquetats o índex de símbol. Un llenguatge produït per una gramàtica indexada s'anomena un llenguatge indexat.

## Definició formal

Una gramàtica indexada es defineix com una 5-tupla $G=(N,T,F,P,S)$on:
* $N$és un conjunt de variables o de símbols no terminals
* $T$és un alfabet de símbols terminals
* $F$és un conjunt de símbols índexs o etiquetes
* $S\in N$ és el símbol d'inici
* $P$ és un conjunt finit de regles de producció
A les regles de producció s'afegeix una cadena (stack) $\sigma \in F^{*}$de símbols índex enganxat a cada símbol no terminal $A\in N$, denotat per $A[\sigma ]$. Els símbols terminals poden no dur stacks associats. Per un stack d'índex $\sigma \in F^{*}$ i una cadena $\alpha \in (N\cup T)^{*}$de símbols no terminals, $\alpha [\sigma ]$denota el resultat d'enganxar $[\sigma ]$a cada símbol no terminal d'$\alpha$.
Per exemple, si $\alpha$és igual a $aBCdE$ amb $a,d\in T$símbols terminals i $B,C,E\in N$símbols no terminals, llavors $\alpha [\sigma ]$denota $aB[\sigma ]C[\sigma ]dE[\sigma ]$. Seguint aquesta notació, cada regla de producció $P$ha de ser de la forma:
* $A[\sigma ]\rightarrow \alpha [\sigma ]$,
* $A[\sigma ]\rightarrow B[f\sigma ]$o
* $A[f\sigma ]\rightarrow \alpha [\sigma ]$
On $A,B\in N$son símbols no terminals, $f\in F$és un índex, $\sigma \in F^{*}$és una cadena de símbols d'índex i $\alpha \in (N\cup T)^{*}$és una cadena de símbols no terminals (alguns autors fan servir "..." enlloc de $\sigma$.
Les derivacions son similars a les de les gramàtiques lliures de context excepte per l'stack de símbols índex per cada símbol no terminal. Quan s'aplica una regla de producció com $A[\sigma ]\rightarrow B[\sigma ]C[\sigma ]$, l'stack d'A es copia a B i C. A més, una regla pot afegir un símbol d'índex a l'stack o treure el de més a l'esquerra.
Formalment, la relació $\Rightarrow$("derivació directa") es defineix en el conjunt $(N[F^{*}]\cup T)^{*}$com segueix:
* Si $A[\sigma ]\rightarrow \alpha [\sigma ]$és una regla de producció de tipus 1, llavors $\beta A[\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma$. Això és, l'stack $\phi$ de la part esquerra de la regla de producció es copia a cada símbol no terminal de la part dreta.
* Si $A[\sigma ]\rightarrow B[f\sigma ]$és una regla de producció de tipus 2, llavors $\beta A[\phi ]\gamma \Rightarrow \beta B[f\phi ]\gamma$. Això és, l'stack d'índex de la part dreta s'obté de l'stack $\phi$ de la part esquerra afegint $f$.
* Si $A[f\sigma ]\rightarrow \alpha [\sigma ]$és una regla de producció de tipus 3, llavors $\beta A[f\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma$, fent servir la definició de $\alpha [\sigma ]$. Això és, el primer índex $f$es treu de l'stack de la part esquerra i es distribueix a cada símbol no terminal de la part dreta.

## Exemples

A la pràctica, stacks d'índexs poden comptar i recordar quines regles s'han aplicat i en quin ordre. Per exemple, les gramàtiques indexades poden descriure llenguatges sensibles al context de paraules triples $\{www:w\in \{a,b\}^{*}\}$:
    S[σ] → S[fσ] T[fσ] → a T[σ] S[σ] → S[gσ] T[gσ] → b T[σ] S[σ] → T[σ] T[σ] T[σ]  T → ε
Una derivació de abbabbabb és:
    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.

## Vegeu també

* Jerarquia de Chomsky
* Llenguatge indexat

## Referències

* ↑ Aho, Alfred V. «Indexed Grammars—An Extension of Context-Free Grammars». J. ACM, 15, 4, 01-10-1968, pàg. 647–671. DOI: 10.1145/321479.321488. ISSN: 0004-5411.
* ↑ Hayashi, Takeshi «On Derivation Trees of Indexed Grammars – An Extension of the uvwxy-Theorem». Publications of the Research Institute for Mathematical Sciences, 9, 1, 30-04-1973, pàg. 61–92. DOI: 10.2977/prims/1195192738. ISSN: 0034-5318.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :