Indeksirani jezik

Indeksirani jezik je formalni jezik kojeg je otkrio Alfred Aho, i koji je pravi podskup skupa svih kontekstno ovisnih jezika i pravi nadskup skupa svih kontekstno neovisnih jezika. Indeksirani jezici mogu biti oblika:

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

Minimalna gramatika koja generira indeksirani jezik jest indeksirana gramatika, a automat koji ga prihvaća jest automat s ugniježđenim stogom. Indeksirana gramatika može imati stog pridodan nezavršnim znakovima koji se kopiraju u nezavršne znakove kćeri. Pored dodavanja i uzimanja znakova sa stoga, automat s ugniježđenim stogom može i čitati sadržaj stoga. Također, stog može ugnijezditi druge stogove unutar sebe.

Vidjeti također

• Chomskyjeva hijerarhija

Vanjske poveznice

• "NLP in Prolog" poglavlje o indeksiranim gramatikama i jezicima