Indeksirani jezik: razlika između inačica

'''Indeksirani jezik''' je [[formalni jezik]] kojeg je otkrio [[Alfred Aho]], i koji je pravi [[podskup]] skupa svih [[kontekstno ovisni jezik|kontekstno ovisnih jezika]] i pravi nadskup skupa svih [[kontekstno neovisni jezik|kontekstno neovisnih jezika]].<ref> {{cite journal | last = [[Alfred Aho|Aho]] | first = Alfred | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [[Journal of the ACM]] | volume = 15 | issue = 4 | pages = 647–671 }} </ref> Indeksirani jezici mogu biti oblika:

:<math> L = \{a^n b^n c^n | n \geq 1 \} </math> <ref> {{cite book | last last1= [[John Hopcroft|Hopcroft]] | first first1= John | coauthors last2=Ullman|first2= [[Jeffrey Ullman]] | title = [[Introduction to automata theory, languages, and computation]] | year = 1979 | publisher = Addison-Wesley | pages = 390 }} </ref>

Minimalna gramatika koja generira indeksirani jezik jest [[indeksirana gramatika]], a automat koji ga prihvaća jest [[automat sa ugniježđenim stogom]]. Indeksirana gramatika može imati [[stog]] pridodan [[završni i nezavršni znakovi|nezavršnim znakovima]] koji se kopiraju u nezavršne znakove ''kćeri''. Pored dodavanja i uzimanja znakova sa stoga, automat sa ugniježđenim stogom može i čitati sadržaj stoga. Također, stog može ugnijezditi druge stogove unutar sebe. <ref> {{cite book | last last1= [[Barbara Partee|Partee]] | first first1= Barbara | coauthors last2= Alice ter Meulen, and|first2=Alice |last3=Wall|first3=Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 }} </ref>