Indeksirana gramatika

Indeksirana gramatika je formalna gramatika koja opisuje indeksirane jezike. Indeksirane gramatike imaju tri diskjunktna skupa simbola: pored uobičajenih završnih i nezavršnih simbola sadrži i indekse, koji se pojavljuju samo u središnjim koracima izvođenja.

Pravila izvođenja mogu da zamene nezavršni simbol niskom završnih i nezavršnih simbola kao u kontekstno slobodnim gramatikama, ali mogu takođe da zamene nezavršni simbol nezavršnim simbolom iza koga sledi indeks, kao i nezavršni simbol iza koga sledi indeks nezavršnim simbolom.

Indeksi mogu da se pojavljuju samo nakon nezavršnog simbola ili drugog indeksa, tako da svaki nezavršni simbol može da se smatra vlasnikom indekasa koji slede iza njega, a koji formiraju stek.

U praksi, stekovi indekasa mogu da broje i pamte koja pravila su primenjena kojim redosledom. Na primer, indeksirane gramatike mogu da opišu ovaj ne-kontekstno slobodni jezik:

L=\{a^{n}b^{n}c^{n}|n\geq 1\}

^[1]

sledećim skupom pravila izvođenja (f and g su indeksi):

$S\to aAfc$

$A\to aAgc~|~B$

$Bf\to b$

$Bg\to bB$

Stek g-ova koji raste u sredini broji koliko puta ( $n-1$ ) je A bilo zamenjeno jednim a i jednim c; svako g na kraju postaje završni simbol b.

Problem određivanja da li datu nisku prepoznaje data indeksirana gramatika je NP-kompletan.^[1]

Linearne indeksirane gramatike uredi

Džerald Gazdar je definisao drugu klasu, linearno indeksiranih gramatika, zahtevajući da najviše jedan neterminal u svakom koraku izvođenja bude određen za primanje steka; u klasičnoj indeksiranoj gramatici svi nezavršni simboli primaju kopije steka. On je pokazao da ova nova klasa gramatika definiše strogo manju klasu jezika, blago kontekstno osetljive jezike. Da li nisku prepoznaje linearna indeksirana gramatika se može utvrditi u polinomijalnom vremenu.^[2]

Vidi još uredi

Reference uredi

^ ^a ^b Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. str. 390-. ISBN 978-0-201-02988-8.
^ Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ur.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. str. 69-94.

Literatura uredi

Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. ISBN 978-0-201-02988-8.
Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ur.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. str. 69-94.

Spoljašnje veze uredi

NLP u Prologu, poglavlje o indeksiranim gramatikama i jezicima

[Hopcroft_and_Ullman-1] Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. str. 390-. ISBN 978-0-201-02988-8.

[gazdar1998-2] Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ur.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. str. 69-94.

[1]

[2]