Встроенный автомат с выдвижным механизмом

Встроенный автомат с выталкиванием вниз или EPDA — это вычислительная модель для синтаксического анализа языков, созданных с помощью древовидных грамматик (TAG). Он похож на контекстно-свободного анализа автомат грамматики , но вместо использования простого стека для хранения символов он имеет стек итерированных стеков, в которых хранятся символы, что дает TAG генеративную способность между контекстно-свободными и контекстно-зависимыми грамматиками. или подмножество слегка контекстно-зависимых грамматик . Встроенные автоматы с выталкиванием вниз не следует путать с автоматами со вложенным стеком , которые обладают большей вычислительной мощностью.

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

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

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

Теория

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

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

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

$\,M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Q_{\textrm {F}},\sigma _{0})$ где

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

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

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

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

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

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

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

Неофициальное описание EPDA можно также найти у Джоши, Шабеса (1997), Раздел 7, с. 23-25.

EPDA k иерархия

Более точно определенная иерархия языков, соответствующих слабо контекстно-зависимому классу, была определена Дэвидом Дж. Вейром. На основе работы Набиля А. Хаббаза: Иерархия языка управления Вейра представляет собой иерархию, состоящую из счетного набора языковых классов. где Уровень-1 определен как контекстно-свободный, а Уровень-2 — это класс присоединения дерева и трех других грамматик.

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

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

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

См. также

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

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

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