Индексированный язык - Indexed language

Проиндексированные языки являются классом формальные языки обнаружен Альфред Ахо;[1] они описаны индексированные грамматики и может быть признан вложенные стековые автоматы.[2]

Проиндексированные языки - это правильное подмножество из контекстно-зависимые языки.[1] Они квалифицируются как абстрактная семья языков (кроме того, полный AFL) и, следовательно, удовлетворяют многим свойствам замыкания. Однако они не замыкаются на пересечение или дополнение.[1]

Класс индексируемых языков имеет практическое значение в обработка естественного языка как вычислительно доступный[нужна цитата ] обобщение контекстно-свободные языки, поскольку индексированные грамматики может описывать многие нелокальные ограничения, встречающиеся в естественных языках.

Джеральд Газдар (1988)[3] и Виджай-Шанкер (1987)[4] представил слегка контекстно-зависимый язык класс, теперь известный как линейные индексированные грамматики (LIG).[5] У линейных индексированных грамматик есть дополнительные ограничения по сравнению с IG. LIG слабо эквивалентный (создать тот же языковой класс), что и дерево смежных грамматик.[6]

Примеры

Следующие языки проиндексированы, но не контекстно-свободный:

[3]
[2]

Эти два языка тоже проиндексированы, но даже не слегка контекстно-зависимый по характеристике Газдара:

[2]
[3]

С другой стороны, не индексируется следующий язык:[7]

Характеристики

Хопкрофт и Ульман склонны рассматривать индексированные языки как "естественный" класс, поскольку они порождаются несколькими формализмами, такими как:[9]

Хаяси[14] обобщил лемма о накачке к индексированным грамматикам. И наоборот, Гилман[7] дает «лемму сжатия» для индексированных языков.

Смотрите также

Рекомендации

  1. ^ а б c d Ахо, Альфред (1968). «Индексированные грамматики - расширение контекстно-свободных грамматик». Журнал ACM. 15 (4): 647–671. Дои:10.1145/321479.321488. S2CID  9539666.
  2. ^ а б c Парти, Барбара; тер Мейлен, Алиса; Уолл, Роберт Э. (1990). Математические методы в лингвистике. Kluwer Academic Publishers. С. 536–542. ISBN  978-90-277-2245-4.
  3. ^ а б c Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». In Reyle, U .; Рорер, К. (ред.). Анализ естественного языка и лингвистические теории. Исследования в области лингвистики и философии. 35. Springer Нидерланды. С. 69–94. Дои:10.1007/978-94-009-1337-0_3. ISBN  978-94-009-1337-0.
  4. ^ Виджаяшанкер, К. (1987). Изучение дерева смежных грамматик (Тезис). ProQuest  303610666.
  5. ^ Каллмейер, Лаура (2010). Анализ вне контекстно-свободных грамматик. Springer. п. 31. ISBN  978-3-642-14846-0.
  6. ^ Каллмейер, Лаура (16 августа 2010 г.). Анализ вне контекстно-свободных грамматик. Springer. п. 32. ISBN  978-3-642-14846-0.
  7. ^ а б Гилман, Роберт Х. (1996). «Лемма о сжатии для индексированных языков». Теоретическая информатика. 163 (1–2): 277–281. arXiv:математика / 9509205. Дои:10.1016/0304-3975(96)00244-7. S2CID  14479068.
  8. ^ Хопкрофт, Джон; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. п. 390. ISBN  978-0-201-02988-8.
  9. ^ Введение в теорию автоматов, языки и вычисления,[8] Библиографические примечания, с.394-395
  10. ^ Ахо, Альфред В. (июль 1969 г.). «Вложенные автоматы стека». Журнал ACM. 16 (3): 383–406. Дои:10.1145/321526.321529. S2CID  685569.
  11. ^ Фишер, Майкл Дж. (Октябрь 1968 г.). Грамматики с макроподобными произведениями. 9-й ежегодный симпозиум по теории коммутации и автоматов (swat 1968). С. 131–142. Дои:10.1109 / SWAT.1968.12.
  12. ^ Грейбах, Шейла А. (март 1970 г.). «Полные AFL и вложенная повторная подстановка». Информация и контроль. 16 (1): 7–35. Дои:10.1016 / s0019-9958 (70) 80039-0.
  13. ^ Майбаум, Т.С.Э. (Июнь 1974 г.). «Обобщенный подход к формальным языкам». Журнал компьютерных и системных наук. 8 (3): 409–439. Дои:10.1016 / s0022-0000 (74) 80031-0.
  14. ^ Хаяси, Такеши (1973). "О деревьях вывода индексированных грамматик: расширение {$ uvwxy $} - теоремы". Публикации НИИ математических наук. 9 (1): 61–92. Дои:10.2977 / prims / 1195192738.

внешняя ссылка