Изменения
Нет описания правки
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках [[Удаление_цепных_правил_из_грамматики|без цепных правил]] и [[Удаление_eps-правил_из_грамматики|без <tex>\varepsilon</tex>-правил]].
== Алгоритм для произвольной грамматики ==
Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j-1]\right]</tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма.
Также введём вспомогательный трехмерный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true</tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>.
* '''База динамики''':
== Оценка сложности ==
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</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> памяти.
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
