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 on:
és un conjunt de variables o de símbols no terminals és un alfabet de símbols terminals és un conjunt de símbols índexs o etiquetes és el símbol d'inici és un conjunt finit de regles de producció
A les regles de producció s'afegeix una cadena (stack) de símbols índex enganxat a cada símbol no terminal , denotat per . Els símbols terminals poden no dur stacks associats. Per un stack d'índex i una cadena de símbols no terminals, denota el resultat d'enganxar a cada símbol no terminal d'.
Per exemple, si és igual a amb símbols terminals i símbols no terminals, llavors denota . Seguint aquesta notació, cada regla de producció ha de ser de la forma:
, o
On son símbols no terminals, és un índex, és una cadena de símbols d'índex i és una cadena de símbols no terminals (alguns autors fan servir "..." enlloc de .
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 , 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ó ("derivació directa") es defineix en el conjunt com segueix:
Si és una regla de producció de tipus 1, llavors . Això és, l'stack de la part esquerra de la regla de producció es copia a cada símbol no terminal de la part dreta. Si és una regla de producció de tipus 2, llavors . Això és, l'stack d'índex de la part dreta s'obté de l'stack de la part esquerra afegint . Si és una regla de producció de tipus 3, llavors , fent servir la definició de . Això és, el primer índex 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 :
|S[σ] |→ |S[fσ] |T[fσ] |→ |a T[σ] |- |S[σ] |→ |S[gσ] |T[gσ] |→ |b T[σ] |- |S[σ] |→ |T[σ] T[σ] T[σ] |T[] |→ |ε
Una derivació de abbabbabb és:
⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ .
Vegeu també Jerarquia de Chomsky Llenguatge indexat
Referències
Categoria:Màquines de Turing Categoria:Complexitat computacional