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

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

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

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

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

Примеры

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

{ а н б н с н г н | н ≥ 1 } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}} [3]
{ а н б м с н г м | м , н ≥ 0 } {\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}} [2]

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

{ а 2 н | н ≥ 0 } {\displaystyle \{a^{2^{n}}|n\geq 0\}} [2]
{ ж ж ж | ж ∈ { а , б } + } {\displaystyle \{www|w\in \{a,b\}^{+}\}} [3]

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

{ ( а б н ) н | н ≥ 0 } {\displaystyle \{(ab^{n})^{n}|n\geq 0\}}

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

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

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

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

Ссылки

  1. ^ abcd Ахо, Альфред (1968). «Индексированные грамматики — расширение контекстно-свободных грамматик». Журнал ACM . 15 (4): 647–671. doi : 10.1145/321479.321488 . S2CID  9539666.
  2. ^ abc Partee, Barbara ; ter Meulen, Alice ; Wall, Robert E. (1990). Математические методы в лингвистике . Kluwer Academic Publishers. стр. 536–542. ISBN 978-90-277-2245-4.
  3. ^ abc Gazdar, Gerald (1988). "Применимость индексированных грамматик к естественным языкам". В Reyle, U.; Rohrer, C. (ред.). Анализ естественного языка и лингвистические теории . Исследования по лингвистике и философии. Т. 35. Springer Netherlands. стр. 69–94. doi :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. ^ ab Gilman, Robert H. (1996). "Лемма сокращения для индексированных языков". Теоретическая информатика . 163 (1–2): 277–281. arXiv : math/9509205 . doi :10.1016/0304-3975(96)00244-7. S2CID  14479068.
  8. ^ Хопкрофт, Джон ; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления. Addison-Wesley. стр. 390. ISBN 978-0-201-02988-8.
  9. ^ Введение в теорию автоматов, языков и вычислений, [8] Библиографические примечания, стр.394-395
  10. ^ Ахо, Альфред В. (июль 1969). «Вложенные стековые автоматы». Журнал ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID  685569.
  11. ^ Фишер, Майкл Дж. (октябрь 1968 г.). «Грамматики с макроподобными производствами». 9-й ежегодный симпозиум по теории коммутации и автоматов (Swat 1968 г.) . 9-й ежегодный симпозиум по теории коммутации и автоматов (Swat 1968 г.). стр. 131–142. doi :10.1109/SWAT.1968.12.
  12. ^ Грейбах, Шейла А. (март 1970 г.). «Полные AFL и вложенная итеративная подстановка». Информация и управление . 16 (1): 7–35. doi :10.1016/s0019-9958(70)80039-0.
  13. ^ Maibaum, TSE (июнь 1974). «Обобщенный подход к формальным языкам». Журнал компьютерных и системных наук . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .
  14. ^ Хаяси, Такеси (1973). «О деревьях вывода индексированных грамматик: расширение теоремы {$uvwxy$}». Публикации Научно-исследовательского института математических наук . 9 (1): 61–92. doi : 10.2977/prims/1195192738 .
  • Глава «NLP в Prolog» об индексированных грамматиках и языках
Получено с "https://en.wikipedia.org/w/index.php?title=Индексированный_язык&oldid=1193213108"