Встроенный магазинный автомат или EPDA является вычислительной моделью для разбора языков , порождаемых дерев прилегающих грамматик (TAGS). Он похож на автомат контекстно-свободного разбора грамматики , но вместо использования простого стека для хранения символов он имеет стек повторяющихся стеков, в которых хранятся символы, что дает тегам возможность генерации между контекстно-независимыми и контекстно-зависимыми грамматиками. , или подмножество слегка контекстно-зависимых грамматик . Не следует путать встроенные автоматы выталкивания с автоматами с вложенными стеками, которые обладают большей вычислительной мощностью. [цитата необходима ]
История и приложения
EPDA были впервые описаны К. Виджай-Шанкером в его докторской диссертации 1988 г. [1] С тех пор они применялись для более полных описаний классов слегка контекстно-зависимых грамматик и сыграли важную роль в уточнении иерархии Хомского . Таким образом, могут быть определены различные подграмматики, такие как линейная индексированная грамматика . [2] EPDA также начинают играть важную роль в обработке естественного языка.
Хотя естественные языки традиционно анализировались с использованием контекстно-свободных грамматик (см. Трансформационно-генеративная грамматика и вычислительная лингвистика ), эта модель не работает для языков со скрещенными зависимостями, таких как голландский, ситуаций, для которых хорошо подходит EPDA. Подробный лингвистический анализ доступен у Joshi, Schabes (1997). [3]
Теория
EPDA - это конечный автомат с набором стеков, к которым можно получить доступ через встроенный стек . Каждый стек содержит элементы алфавита стека , поэтому мы определяем элемент стека как , где звездочка - это замыкание алфавита Клини .
Затем каждый стек можно определить в терминах его элементов, поэтому мы обозначаем th стек в автомате с использованием символа двойного кинжала: , [ требуется пояснение ] гдебудет следующим доступным символом в стеке. Встроенный стек из стеки, таким образом, могут быть обозначены . [ требуется разъяснение ]
Мы определяем EPDA семеркой (семеркой)
- где
- - конечный набор состояний ;
- - конечное множество входного алфавита ;
- - конечный стековый алфавит ;
- это начальное состояние ;
- - множество конечных состояний ;
- это начальный символ стека
- - функция перехода , где конечные подмножества .
Таким образом, функция перехода принимает состояние, следующий символ входной строки и верхний символ текущего стека и генерирует следующее состояние, стеки, которые должны быть помещены и выталкиваются во встроенный стек , проталкивание и выталкивание текущего стека. , и стеки будут считаться текущими стеками при следующем переходе. Более концептуально, встроенный стек выталкивается и выталкивается, текущий стек необязательно перемещается обратно во встроенный стек , а любые другие стеки, которые вы хотели бы, помещаются поверх него, причем последний стек является тем, из которого читается в следующей итерации. . Следовательно, стеки можно помещать как выше, так и ниже текущего стека.
Данная конфигурация определяется
где текущее состояние, s - это стеки во встроенном стеке , причем текущий стек, а для входной строки , это часть строки, уже обработанная машиной, и - это часть, которая должна быть обработана, с заголовком, являющимся текущим считанным символом. Обратите внимание, что пустая строканеявно определяется как завершающий символ, где, если машина находится в конечном состоянии при чтении пустой строки, вся входная строка принимается , а если нет, она отклоняется . Такие принятые строки являются элементами языка
где а также определяет функцию перехода, применяемую столько раз, сколько необходимо для анализа строки.
Неформальное описание EPDA также можно найти в Joshi, Schabes (1997), [3] Sect.7, p. 23-25.
k -порядок EPDA и иерархия Weir
Более точно определенная иерархия языков, которые соответствуют умеренно контекстно-зависимому классу, была определена Дэвидом Дж. Вейром. [4] На основе работы Набиля А. Хаббаза, [5] [6] Иерархия языка управления Weir представляет собой иерархию включения счетного набора языковых классов [ пояснить ], где Уровень-1 определяется как контекстно-свободный, а Уровень -2 - это класс смежных с деревом и трех других грамматик.
Ниже приведены некоторые свойства языков Level- k в иерархии:
- Языки Level- k должным образом содержатся в языковом классе Level- ( k + 1).
- Языки уровня k можно анализировать в время
- Уровень- k содержит язык, но нет
- Уровень- k содержит язык, но нет
Эти свойства хорошо соответствуют (по крайней мере, для малых k > 1) условиям умеренно контекстно-зависимых языков, наложенных Джоши, и по мере того, как k становится больше, языковой класс в некотором смысле становится менее контекстно-зависимым.
Смотрите также
Рекомендации
- ↑ Виджай-Шанкер, К. (январь 1988 г.). «Исследование грамматик, примыкающих к дереву» . Кандидат наук. Тезис . Пенсильванский университет .
- ^ Вейр, Дэвид Дж. (1994). «Линейные повторяющиеся выталкивания вниз» (PDF) . Вычислительный интеллект . 10 (4): 431–439. DOI : 10.1111 / j.1467-8640.1994.tb00007.x . Проверено 20 октября 2012 .
- ^ а б Джоши, Аравинд К .; Ив Шабес (1997). «Грамматики, примыкающие к дереву» (PDF) . Справочник формальных языков . Springer. 3 : 69–124. DOI : 10.1007 / 978-3-642-59126-6_2 . ISBN 978-3-642-63859-6. Проверено 7 февраля 2014 .
- ^ Weir, DJ (1992), "Геометрическая иерархия вне контекстно-свободных языков", Теоретическая информатика , 104 (2): 235-261, DOI : 10,1016 / 0304-3975 (92) 90124-X .
- ^ Набиль Антон Хаббаз (1972). Обобщенные контекстно-свободные языки (Ph.D.). Университет Айовы.
- ^ Набиль Антон Хаббаз (1974). «Геометрическая иерархия языков». J. Comput. Syst. Sci . 8 (2): 142–157. DOI : 10.1016 / s0022-0000 (74) 80052-8 .
дальнейшее чтение
- Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик . Springer Science & Business Media. ISBN 978-3-642-14846-0.