Индексиран језик

Индексирани језици су класа формалних језика које је открио Алфред Ахо^[1]; они су описани индексираним граматикама а могу да их препознају аутомати са угњежденим стеком.^[2].

Индексирани језици представљају прави подскуп скупа контекстно-сензитивних језика и прави надскуп скупова благо контекстно-сензитивних језика и контекстно-слободних језика. Квалификују се као апстрактна фамилија језика и стога задовољавају многа својства затворења. Међутим, они нису затворени у односу на пресек или комплемент.^[1] Џералд Газдар је карактерисао благо контекстно-сензитивне језике преко линеарних индексираних граматика.^[3]

Класа индексираних језика има практичан значај у процесирању природних језика као рачунски прихватљива генерализација контекстно-слободних језика, јер индексиране граматике могу да опишу многа од нелокалних ограничења која се јављају у природним језицима.

Примери

Следећи језици јесу индексирани али нису контекст-слободни:

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

^[3]

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

^[2]

Ова два језика су индексирана али нису чак ни благо контекстно-сензитивни по Газдаровој карактеризацији:

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

^[2]

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

^[3]

Са друге стране, следећи језик није индексиран^[4]:

{(a b^{n})^{n} | n \geq 0}