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

Индексирани језици су класа формалних језика које је открио Алфред Ахо^[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]

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

^[3]

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

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

^ ^а ^б Aho, Alfred (1968). „Indexed grammars—an extension of context-free grammars”. Journal of the ACM]]. 15 (4): 647—671. doi:10.1145/321479.321488.
^ ^а ^б ^в Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. стр. 536–542. ISBN 978-90-277-2245-4.
^ ^а ^б ^в Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ур.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69–94.
^ Gilman, Robert (1996). „A shrinking lemma for indexed languages”. Theoretical Computer Science. 163 (1-2): 277—281. doi:10.1016/0304-3975(96)00244-7.

Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. стр. 536–542. ISBN 978-90-277-2245-4.
Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ур.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69–94.