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

Из Википедије, слободне енциклопедије

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

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

Види још[уреди]

Референце[уреди]

  1. ^ а б Aho, Alfred (1968). „Indexed grammars—an extension of context-free grammars“. Journal of the ACM]] 15 (4): 647–671. DOI:10.1145/321479.321488. 
  2. ^ а б в 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. 
  3. ^ а б в Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages“. In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69–94. 
  4. ^ 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“. In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69–94. 

Спољашње везе[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.