Gramàtica indexada

De Viquipèdia
Salta a la navegació Salta a la cerca

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[modifica]

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:

  1. ,
  2. 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:

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

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[] T[] a T[σ]
S[σ] S[] T[] 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é[modifica]

Referències[modifica]

  1. Aho, Alfred V. «Indexed Grammars—An Extension of Context-Free Grammars». J. ACM, 15, 4, 1968-10, pàg. 647–671. DOI: 10.1145/321479.321488. ISSN: 0004-5411.
  2. 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.