Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики

2017-01-17T12:29:26Z

94.25.229.7: Красиво оформлен алгоритм

Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.

[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках [[Удаление_цепных_правил_из_грамматики|без цепных правил]] и [[Удаление_eps-правил_из_грамматики|без <tex>\varepsilon</tex>-правил]].

== Алгоритм для произвольной грамматики ==
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.

Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма.

Также введём вспомогательный трехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true</tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..j\right]</tex>.

* '''База динамики''':

<tex>a\left[A, i, i\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе <tex>a\left[A, i, i\right] = false</tex>;

<tex>a\left[A, i, i-1\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow \varepsilon</tex>, иначе <tex>a\left[A, i, i-1\right] = false</tex>;

<tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i-1, 0\right] = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов правил.

* '''Переход''': Пусть для всех подстрок <tex>w[i..j]</tex> динамики уже вычислены. Сначала вычислим вспомогательную динамику: <tex>\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i-1..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j\right]\right)</tex>. Это вычисление может обратится к <tex>a\left[A,i,j\right]</tex>, но на результат это не повлияет, так так в данный момент <tex>a\left[A,i,j\right]=false</tex>.

Главная динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right]</tex>.

* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.

== Оценка сложности ==
Расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex> времени, основной динамики — <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex> памяти.

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Викиконспекты - Вклад участника [ru]

Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики