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:

1. $A[\sigma ]\rightarrow \alpha [\sigma ]$,
2. $A[\sigma ]\rightarrow B[f\sigma ]$o
3. $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:

1. 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.
2. 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$.
3. 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