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.^[1][2]

Definició formal

Una gramàtica indexada es defineix com una 5-tupla ${\displaystyle G=(N,T,F,P,S)}$on:

• ${\displaystyle N}$és un conjunt de variables o de símbols no terminals
• ${\displaystyle T}$és un alfabet de símbols terminals
• ${\displaystyle F}$és un conjunt de símbols índexs o etiquetes
• ${\displaystyle S\in N}$ és el símbol d'inici
• ${\displaystyle P}$ és un conjunt finit de regles de producció

A les regles de producció s'afegeix una cadena (stack) ${\displaystyle \sigma \in F^{*}}$de símbols índex enganxat a cada símbol no terminal ${\displaystyle A\in N}$, denotat per ${\displaystyle A[\sigma ]}$. Els símbols terminals poden no dur stacks associats. Per un stack d'índex ${\displaystyle \sigma \in F^{*}}$ i una cadena ${\displaystyle \alpha \in (N\cup T)^{*}}$de símbols no terminals, ${\displaystyle \alpha [\sigma ]}$denota el resultat d'enganxar ${\displaystyle [\sigma ]}$a cada símbol no terminal d'${\displaystyle \alpha }$.

Per exemple, si ${\displaystyle \alpha }$és igual a ${\displaystyle aBCdE}$ amb ${\displaystyle a,d\in T}$símbols terminals i ${\displaystyle B,C,E\in N}$símbols no terminals, llavors ${\displaystyle \alpha [\sigma ]}$denota ${\displaystyle aB[\sigma ]C[\sigma ]dE[\sigma ]}$. Seguint aquesta notació, cada regla de producció ${\displaystyle P}$ha de ser de la forma:

1. ${\displaystyle A[\sigma ]\rightarrow \alpha [\sigma ]}$,
2. ${\displaystyle A[\sigma ]\rightarrow B[f\sigma ]}$o
3. ${\displaystyle A[f\sigma ]\rightarrow \alpha [\sigma ]}$

On ${\displaystyle A,B\in N}$son símbols no terminals, ${\displaystyle f\in F}$és un índex, ${\displaystyle \sigma \in F^{*}}$és una cadena de símbols d'índex i ${\displaystyle \alpha \in (N\cup T)^{*}}$és una cadena de símbols no terminals (alguns autors fan servir "..." enlloc de ${\displaystyle \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 ${\displaystyle 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ó ${\displaystyle \Rightarrow }$("derivació directa") es defineix en el conjunt ${\displaystyle (N[F^{*}]\cup T)^{*}}$com segueix:

1. Si ${\displaystyle A[\sigma ]\rightarrow \alpha [\sigma ]}$és una regla de producció de tipus 1, llavors ${\displaystyle \beta A[\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma }$. Això és, l'stack ${\displaystyle \phi }$ de la part esquerra de la regla de producció es copia a cada símbol no terminal de la part dreta.
2. Si ${\displaystyle A[\sigma ]\rightarrow B[f\sigma ]}$és una regla de producció de tipus 2, llavors ${\displaystyle \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 ${\displaystyle \phi }$ de la part esquerra afegint ${\displaystyle f}$.
3. Si ${\displaystyle A[f\sigma ]\rightarrow \alpha [\sigma ]}$és una regla de producció de tipus 3, llavors ${\displaystyle \beta A[f\phi ]\gamma \Rightarrow \beta \alpha [\phi ]\gamma }$, fent servir la definició de ${\displaystyle \alpha [\sigma ]}$. Això és, el primer índex ${\displaystyle 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 ${\displaystyle \{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