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

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

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

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

Примери

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

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

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

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

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

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

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

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

Види још

• Хијерархија Чомског
• Индексирана граматика
• Благо контекстно осетљиви језик

Спољашње везе

• НЛП у Прологу, поглавље о индексираним граматикама и језицима