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

редактировать

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

Содержание

1 История и приложения
2 Теория
EPDA 3 k-го порядка и Weir иерархия
4 См. также
5 Ссылки
6 Дополнительная литература

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

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

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

Теория

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

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

Мы определяем EPDA по семерке (кортеж из семи)

M = (Q, Σ, Γ, δ, q 0, QF, σ 0) {\ displaystyle \, M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, Q _ {\ textrm {F}}, \ sigma _ {0})}

\, M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, Q _ {{\ textrm {F}}}, \ sigma _ {0})

где

$Q {\ displaystyle \, Q}$ $\, Q$ - конечный набор состояний;
$Σ {\ displaystyle \, \ Sigma}$ $\, \ Sigma$ - конечный набор входного алфавита;
$Γ {\ displaystyle \, \ Gamma}$ $\, \ Gamma$ - алфавит конечного стека;
$q 0 ∈ Q {\ displaystyle \, q_ {0} \ in Q}$ $\, q_ {0} \ in Q$ - начальное состояние;
$QF ⊆ Q {\ displaystyle \, Q _ {\ textrm {F}} \ substeq Q}$ $\, Q _ {{\ textrm {F} }} \ substeq Q$ - это набор конечных состояний;
$σ 0 ∈ Γ {\ displaystyle \, \ sigma _ {0} \ in \ Gamma}$ $\, \ sigma _ { 0} \ in \ Gamma$ - начальный символ стека
$δ: Q × Σ × Γ → S {\ Displaystyle \, \ дельта: Q \ times \ Sigma \ times \ Gamma \ rightarrow S}$ $\, \ delta: Q \ times \ Sigma \ times \ Gamma \ стрелка вправо S$ - функция перехода, где $S {\ displaystyle \, S}$ $\, S$ - конечные подмножества $Q × ( ‡ Γ +) ∗ × Γ ∗ × (‡ Γ +) ∗ {\ displaystyle \, Q \ times (\ ddagger \ Gamma ^ {+}) ^ {*} \ times \ Gamma ^ {*} \ times (\ ddagger \ Gamma ^ {+}) ^ {*}}$ $\, Q \ times (\ ddagger \ Gamma ^ {+}) ^ {*} \ times \ Gamma ^ {*} \ times (\ ddagger \ Gamma ^ {+}) ^ {*}$ .

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

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

C (M) = {q, Υ m… Υ 1, x 1, x 2} ∈ Q × (‡ Γ +) ∗ × Σ ∗ × Σ ∗. {\ Displaystyle \, С (М) = \ {q, \ Upsilon _ {m} \ ldots \ Upsilon _ {1}, x_ {1}, x_ {2} \} \ in Q \ times (\ ddagger \ Gamma ^ {+}) ^ {*} \ times \ Sigma ^ {*} \ times \ Sigma ^ {*}}

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

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

L (M) = {x | {q 0, Υ 0, ϵ, x} → M ∗ {q F, Υ m… Υ 1, x, ϵ}} {\ displaystyle \, L (M) = \ left \ {x | \ {q_ {0) }, \ Upsilon _ {0}, \ epsilon, x \} \ rightarrow _ {M} ^ {*} \ {q _ {\ textrm {F}}, \ Upsilon _ {m} \ ldots \ Upsilon _ {1}, x, \ epsilon \} \ right \}}

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

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

Неофициальное описание EPDA также можно найти в Joshi, Schabes (1997), Sect.7, p. 23-25.

EPDA k-го порядка и иерархия Weir

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

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

языки уровня k надлежащим образом содержатся в языковом классе Level- (k + 1)
Level- k языков можно проанализировать за $O (n 3 ⋅ 2 k - 1) {\ displaystyle O (n ^ {3 \ cdot 2 ^ {k-1}})}$ $O (n ^ {{3 \ cdot 2 ^ { {k-1}}}})$ времени
Уровень-k содержит язык ${a 1 n… a 2 kn | n ≥ 0} {\ displaystyle \ {a_ {1} ^ {n} \ dotso a_ {2 ^ {k}} ^ {n} | n \ geq 0 \}}$ $\ {a_ {1} ^ {n} \ dotso a _ {{2 ^ {k }}} ^ {n} | n \ geq 0 \}$ , но не ${a 1 n… a 2 k + 1 n | n ≥ 0} {\ displaystyle \ {a_ {1} ^ {n} \ dotso a_ {2 ^ {k + 1}} ^ {n} | n \ geq 0 \}}$ $\ {a_ {1} ^ { n} \ dotso a _ {{2 ^ {{k + 1}}}} ^ {n} | n \ geq 0 \}$
Уровень-k содержит язык ${w 2 k - 1 | вес ∈ {a, b} ∗} {\ displaystyle \ {w ^ {2 ^ {k-1}} | w \ in \ {a, b \} ^ {*} \}}$ $\ {w ^ {{2 ^ {{k-1}}}} | w \ in \ {a, b \} ^ {*} \}$ , но не ${w 2 k - 1 + 1 | w ∈ {a, b} ∗} {\ displaystyle \ {w ^ {2 ^ {k-1} +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.