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

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

История и приложения [ править ]

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

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

Теория [ править ]

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

Каждый стек может быть определен в терминах его элементов, поэтому мы обозначим й стек в автомате , используя символ двойного кинжала: , ^{[ требуется уточнение ]} , где будет следующим доступным символ в стеке. Встроенный стек из стопок , таким образом , может быть обозначен . ^{[ требуется разъяснение ]}${\ displaystyle \, j}$${\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 }$${\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] Sect.7, p. 23-25.

k- порядок EPDA и иерархия Weir [ править ]

Этот раздел может потребовать очистки, чтобы соответствовать стандартам качества Википедии . Конкретная проблема: необходимо переписать на основе Kallmeyer p. 199 Пожалуйста, помогите улучшить этот раздел, если можете. ( Август 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

• Языки Level- k правильно содержатся в языковом классе Level- ( 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 становится больше, языковой класс в некотором смысле становится менее зависимым от контекста.

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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