Indeksiran jezik

Indeksirani jezici su klasa formalnih jezika koje je otkrio Alfred Aho; oni su opisani indeksiranim gramatikama a mogu da ih prepoznaju automati sa ugnježdenim stekom..

Indeksirani jezici predstavljaju pravi podskup skupa kontekstno-senzitivnih jezika i pravi nadskup skupova blago kontekstno-senzitivnih jezika i kontekstno-slobodnih jezika. Kvalifikuju se kao apstraktna familija jezika i stoga zadovoljavaju mnoga svojstva zatvorenja. Međutim, oni nisu zatvoreni u odnosu na presek ili komplement. Džerald Gazdar je karakterisao blago kontekstno-senzitivne jezike preko linearnih indeksiranih gramatika.

Klasa indeksiranih jezika ima praktičan značaj u procesiranju prirodnih jezika kao računski prihvatljiva generalizacija kontekstno-slobodnih jezika, jer indeksirane gramatike mogu da opišu mnoga od nelokalnih ograničenja koja se javljaju u prirodnim jezicima.

Primeri

Sledeći jezici jesu indeksirani ali nisu kontekst-slobodni:

$\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}$

$\{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}$

Ova dva jezika su indeksirana ali nisu čak ni blago kontekstno-senzitivni po Gazdarovoj karakterizaciji:

$\{a^{2^{n}}|n\geq 0\}$

$\{www|w\in \{a,b\}^{+}\}$

Sa druge strane, sledeći jezik nije indeksiran:

$\{(ab^{n})^{n}|n\geq 0\}$

Vidi još

• Hijerarhija Čomskog
• Indeksirana gramatika
• Blago kontekstno osetljivi jezik

Literatura

• Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. str. 536–542. ISBN 978-90-277-2245-4. 
• 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

• NLP u Prologu, poglavlje o indeksiranim gramatikama i jezicima