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

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

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

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

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

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