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

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

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

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

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

• 1 Примеры
• 2 Свойства
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

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

$\{anbncndn\; |\; n\; \ge \; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{n\}\; b\; ^\; \{n\}\; c\; ^\; \{n\}\; d\; ^\; \{n\}\; |\; n\; \backslash \; geq\; 1\; \backslash \}\}$

$\{a\; n\; b\; m\; c\; n\; d\; m\; |\; m,\; n\; \ge \; 0\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{n\}\; b\; ^\; \{m\}\; c\; ^\; \{n\}\; d\; ^\; \{m\}\; |\; m,\; n\; \backslash \; geq\; 0\; \backslash \}\}$

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

$\{a\; 2\; n\; |\; n\; \ge \; 0\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{2\; ^\; \{n\}\}\; |\; n\; \backslash \; geq\; 0\; \backslash \}\}$

$\{ш\; ш\; ш\; |\; w\; \in \; \{a,\; b\}\; +\}\; \{\backslash \; displaystyle\; \backslash \; \{www\; |\; w\; \backslash \; in\; \backslash \; \{a,\; b\; \backslash \}\; ^\; \{+\}\; \backslash \}\}$

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

$\{(abn)\; n\; |\; n\; \ge \; 0\}\; \{\backslash \; displaystyle\; \backslash \; \{(ab\; ^\; \{n\})\; ^\; \{n\}\; |\; n\; \backslash \; geq\; 0\; \backslash \}\}$

Hopcroft и Ullman склонны рассматривать индексированные языки как «естественный» класс, поскольку они генерируются несколькими формализмами, такими как:

• индексированные грамматики Aho
• односторонние вложенные стековые автоматы
• Макро грамматики Фишера
• Автоматы Грейбаха со стеками стеков
• Алгебраическая характеристика Майбаума

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

• Иерархия Хомского
• Индексированная грамматика
• Слегка контекстно-зависимый язык

1. ^ Ахо, Альфред (1968). «Индексированные грамматики - расширение контекстно-свободных грамматик». Журнал ACM. 15(4): 647–671. doi : 10.1145 / 321479.321488. S2CID 9539666.
2. ^ Парти, Барбара ; тер Мейлен, Алиса; Уолл, Роберт Э. (1990). Математические методы в лингвистике. Kluwer Academic Publishers. С. 536–542. ISBN 978-90-277-2245-4.
3. ^ Газдар, Джеральд (1988). «Применимость индексированных грамматик к естественным языкам». In Reyle, U.; Рорер, К. (ред.). Анализ естественного языка и лингвистические теории. Исследования в области лингвистики и философии. 35 . Springer Нидерланды. С. 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. ^ Гилман, Роберт Х. (1996). «Лемма о сжатии для индексированных языков». Теоретическая информатика. 163 (1–2): 277–281. arXiv : math / 9509205. DOI : 10.1016 / 0304-3975 (96) 00244-7. S2CID 14479068.
8. ^Хопкрофт, Джон ; Уллман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. п. 390. ISBN 978-0-201-02988-8.
9. ^Введение в теорию автоматов, языки и вычисления, Библиографические примечания, с.394-395
10. ^Ахо, Альфред В. (Июль 1969 г.). «Вложенные автоматы стека». Журнал ACM. 16 (3): 383–406. doi : 10.1145 / 321526.321529. S2CID 685569.
11. ^Фишер, Майкл Дж. (Октябрь 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. ^Майбаум, Т.С.Э. (Июнь 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.

• Глава «НЛП в Прологе» об индексированных грамматиках и языках