53
правки
Изменения
Новая статья (набросок)
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках.
== Алгоритм для произвольной грамматики ==
Обозначим <tex>M = \max_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.
Введём вспомогательную динамику: <tex>h_{A \rightarrow \alpha, i, j, k} = \left[\alpha\left[1..k\right] \Rightarrow^* w\left[i..j\right]\right] \quad \left(\forall A \rightarrow \alpha \in \Gamma\right)</tex>, где <tex>k \le M</tex> — можно ли из префикса длины <tex>k</tex> правой части данного правила вывести <tex>w\left[i..j\right]</tex>. Также введём динамику <tex>a_{A,i,j} = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично базовой версии алгоритма.
* '''База динамики''': <tex>a_{A, i, i} = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>\forall i \:\: a_{A, i, i-1} = \left[ A \rightarrow \varepsilon \right]</tex> — <tex>\varepsilon</tex>-вывод, <tex>\forall i,A \rightarrow \alpha \:\: h_{A \rightarrow \alpha, i, i-1, 0} = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов.
* '''Переход''':
* '''Завершение''':
== Время работы ==
[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках.
== Алгоритм для произвольной грамматики ==
Обозначим <tex>M = \max_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.
Введём вспомогательную динамику: <tex>h_{A \rightarrow \alpha, i, j, k} = \left[\alpha\left[1..k\right] \Rightarrow^* w\left[i..j\right]\right] \quad \left(\forall A \rightarrow \alpha \in \Gamma\right)</tex>, где <tex>k \le M</tex> — можно ли из префикса длины <tex>k</tex> правой части данного правила вывести <tex>w\left[i..j\right]</tex>. Также введём динамику <tex>a_{A,i,j} = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично базовой версии алгоритма.
* '''База динамики''': <tex>a_{A, i, i} = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>\forall i \:\: a_{A, i, i-1} = \left[ A \rightarrow \varepsilon \right]</tex> — <tex>\varepsilon</tex>-вывод, <tex>\forall i,A \rightarrow \alpha \:\: h_{A \rightarrow \alpha, i, i-1, 0} = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов.
* '''Переход''':
* '''Завершение''':
== Время работы ==
