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