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

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

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

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

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

Теория

EPDA - это конечный автомат с набором стеков, к которым можно получить доступ через встроенный стек. Каждый стек содержит элементы сложить алфавит ${ displaystyle , Gamma}$, поэтому мы определяем элемент стека как ${ Displaystyle , sigma _ {я} 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 , м}$ стеки, таким образом, можно обозначить ${ 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}} substeq Q}$ это набор конечные состояния;
• ${ displaystyle , sigma _ {0} in Gamma}$ это начальный символ стека
• ${ displaystyle , delta: Q times Sigma times Gamma rightarrow S}$ это функция перехода, куда ${ displaystyle , S}$ конечные подмножества ${ Displaystyle , Q раз ( ddagger Gamma ^ {+}) ^ {*} times Gamma ^ {*} times ( ddagger Gamma ^ {+}) ^ {*}}$.

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

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

${ Displaystyle , С (М) = {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 , х = х_ {1} х_ {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

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

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

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

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

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

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

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

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

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

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