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

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

Индексирани језици су класа формалних језика које је открио Алфред Ахо[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. 1,0 1,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. 2,0 2,1 2,2 Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4. 
  3. 3,0 3,1 3,2 Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. pp. 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. pp. 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. pp. 69–94. 

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

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