Встроенный автомат выталкивания - Embedded pushdown automaton

An встроенный автомат выталкивания или же EPDA это вычислительная модель для анализа языков, созданных грамматики, примыкающие к дереву (ТЕГИ). Это похоже на контекстно-свободная грамматика -разбор выталкивающий автомат, но вместо использования простого куча для хранения символов у него есть стек повторяющихся стеков, в которых хранятся символы, что дает тегам возможность генерации между контекстно-независимой и контекстно-зависимые грамматики, или подмножество слегка контекстно-зависимые грамматики.Встроенные автоматические выталкивающие устройства не следует путать с вложенные стековые автоматы которые обладают большей вычислительной мощностью.^{[нужна цитата ]}

История и приложения

EPDA были впервые описаны К. Виджай-Шанкером в его докторской диссертации 1988 г.^[1] С тех пор они были применены к более полным описаниям классов умеренно зависимых от контекста грамматик и сыграли важную роль в уточнении Иерархия Хомского. Различные подграмматики, такие как линейная индексированная грамматика, таким образом можно определить.^[2] EPDA также начинают играть важную роль в обработке естественного языка.

Хотя естественные языки традиционно анализировались с использованием контекстно-свободных грамматик (см. трансформационно-порождающая грамматика и компьютерная лингвистика ), эта модель не работает для языков с перекрестными зависимостями, таких как голландский, ситуаций, для которых хорошо подходит EPDA. Подробный лингвистический анализ доступен у Joshi, Schabes (1997).^[3]

Теория

EPDA - это конечный автомат с набором стеков, к которым можно получить доступ через встроенный стек. Каждый стек содержит элементы сложить алфавит ${\displaystyle \,\Gamma }$, поэтому мы определяем элемент стека как ${\displaystyle \,\sigma _{i}\in \Gamma ^{*}}$, где звезда Клини закрытие алфавита.

Затем каждый стек можно определить в терминах его элементов, поэтому мы обозначаем ${\displaystyle \,j}$th стек в автомате с использованием символа двойного кинжала: ${\displaystyle \,\Upsilon _{j}=\ddagger \sigma _{j}=\{\sigma _{j,k},\sigma _{j,k-1},\ldots ,\sigma _{j,1}\}}$,^{[требуется разъяснение ]} куда ${\displaystyle \,\sigma _{j,k}}$ будет следующим доступным символом в стеке. В встроенный стек из ${\displaystyle \,m}$ стеки, таким образом, можно обозначить ${\displaystyle \,\{\Upsilon _{j}\}=\{\ddagger \sigma _{m},\ddagger \sigma _{m-1},\ldots ,\ddagger \sigma _{1}\}\in (\ddagger \Gamma ^{+})^{*}}$.^{[требуется разъяснение ]}

Мы определяем EPDA семеркой (семеркой)

${\displaystyle \,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})}$ куда

• ${\displaystyle \,Q}$ конечный набор состояния;
• ${\displaystyle \,\Sigma }$ конечный набор вводить алфавит;
• ${\displaystyle \,\Gamma }$ конечный сложить алфавит;
• ${\displaystyle \,q_{0}\in Q}$ это начальное состояние;
• ${\displaystyle \,Q_{\textrm {F}}\subseteq Q}$ это набор конечные состояния;
• ${\displaystyle \,\sigma _{0}\in \Gamma }$ это начальный символ стека
• ${\displaystyle \,\delta :Q\times \Sigma \times \Gamma \rightarrow S}$ это функция перехода, куда ${\displaystyle \,S}$ конечные подмножества ${\displaystyle \,Q\times (\ddagger \Gamma ^{+})^{*}\times \Gamma ^{*}\times (\ddagger \Gamma ^{+})^{*}}$.

Таким образом, функция перехода принимает состояние, следующий символ входной строки и верхний символ текущего стека и генерирует следующее состояние, стеки, которые должны быть помещены и помещены в встроенный стек, нажатие и выталкивание текущего стека, а также стеки, которые будут считаться текущими стеками при следующем переходе. Более концептуально встроенный стек выталкивается и выталкивается, текущий стек необязательно помещается обратно в встроенный стек, и любые другие стеки, которые вы хотите, помещаются поверх этого, причем последний стек будет считываться из следующей итерации. Следовательно, стеки можно помещать как выше, так и ниже текущего стека.

Данная конфигурация определяется

${\displaystyle \,C(M)=\{q,\Upsilon _{m}\ldots \Upsilon _{1},x_{1},x_{2}\}\in Q\times (\ddagger \Gamma ^{+})^{*}\times \Sigma ^{*}\times \Sigma ^{*}}$

куда ${\displaystyle \,q}$ текущее состояние, ${\displaystyle \,\Upsilon }$s - стеки в встроенный стек, с ${\displaystyle \,\Upsilon _{m}}$ текущий стек, а для входной строки ${\displaystyle \,x=x_{1}x_{2}\in \Sigma ^{*}}$, ${\displaystyle \,x_{1}}$ часть строки, уже обработанная машиной, и ${\displaystyle \,x_{2}}$ - это часть, которая должна быть обработана, с заголовком текущего считываемого символа. Обратите внимание, что пустая строка ${\displaystyle \,\epsilon \in \Sigma }$ неявно определяется как символ завершения, где, если машина находится в конечном состоянии при чтении пустой строки, вся входная строка принято, а если нет, то отклоненный. Такой принято строки - это элементы языка

${\displaystyle \,L(M)=\left\{x|\{q_{0},\Upsilon _{0},\epsilon ,x\}\rightarrow _{M}^{*}\{q_{\textrm {F}},\Upsilon _{m}\ldots \Upsilon _{1},x,\epsilon \}\right\}}$

куда ${\displaystyle \,q_{\textrm {F}}\in Q_{\textrm {F}}}$ и ${\displaystyle \,\rightarrow _{M}^{*}}$ определяет функцию перехода, применяемую столько раз, сколько необходимо для анализа строки.

Неофициальное описание EPDA также можно найти в Joshi, Schabes (1997),^[3] Раздел 7, стр. 23-25.

k-заказ EPDA и иерархия Weir

Более точно определенная иерархия языков, которые соответствуют умеренно контекстно-зависимому классу, была определена Дэвидом Дж. Вейром.^[4]На основе работы Набиля А. Хаббаза,^[5][6]Иерархия языка управления Weir является сдерживающим фактором иерархия счетного множества языковых классов^{[уточнить ]} где 1-й уровень определяется как контекстно-свободный, и Уровень 2 - это класс смежных с деревом и трех других грамматик.

Ниже приведены некоторые свойства Level-k языки в иерархии:

• Уровень-k языки правильно содержатся в Уровне- (k + 1) языковой класс
• Уровень-k языки могут быть проанализированы в ${\displaystyle O(n^{3\cdot 2^{k-1}})}$ время
• Уровень-k содержит язык ${\displaystyle \{a_{1}^{n}\dotso a_{2^{k}}^{n}|n\geq 0\}}$, но нет ${\displaystyle \{a_{1}^{n}\dotso a_{2^{k+1}}^{n}|n\geq 0\}}$
• Уровень-k содержит язык ${\displaystyle \{w^{2^{k-1}}|w\in \{a,b\}^{*}\}}$, но нет ${\displaystyle \{w^{2^{k-1}+1}|w\in \{a,b\}^{*}\}}$

Эти свойства хорошо соответствуют (по крайней мере, для небольших k > 1) к условиям умеренно контекстно-зависимых языков, наложенных Джоши, и как k становится больше, языковой класс в некотором смысле становится менее зависимым от контекста.

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

• комбинаторно-категориальная грамматика

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

1. Виджай-Шанкер, К. (январь 1988 г.). "Исследование грамматик, прилегающих к дереву". Кандидат наук. Тезис. Пенсильванский университет.
2. Вейр, Дэвид Дж. (1994). «Линейные повторяющиеся выталкивания вниз» (PDF). Вычислительный интеллект. 10 (4): 431–439. Дои:10.1111 / j.1467-8640.1994.tb00007.x. Получено 2012-10-20.
3. Джоши, Аравинд К .; Ив Шабес (1997). "Грамматики, примыкающие к дереву" (PDF). Справочник формальных языков. Springer. 3: 69–124. Дои:10.1007/978-3-642-59126-6_2. ISBN  978-3-642-63859-6. Получено 2014-02-07.
4. Вейр, Д. Дж. (1992), «Геометрическая иерархия за пределами контекстно-свободных языков», Теоретическая информатика, 104 (2): 235–261, Дои:10.1016 / 0304-3975 (92) 90124-Х.
5. Набиль Антон Хаббаз (1972). Обобщенные контекстно-свободные языки (Кандидат наук.). Университет Айовы.
6. Набиль Антон Хаббаз (1974). «Геометрическая иерархия языков». J. Comput. Syst. Наука. 8 (2): 142–157. Дои:10.1016 / s0022-0000 (74) 80052-8.

дальнейшее чтение

• Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик. Springer Science & Business Media. ISBN  978-3-642-14846-0.