Изменения

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

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

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

Также введём вспомогательный трехмерный массив Рассмотрим все тройки <tex>h\left[A lbrace \rightarrow \alphalangle j, i, \rangle \mid j-i=m \rbrace</tex>, k\right] = trueгде <tex>m</tex> тогда {{---}} константа и только тогда<tex>m < n</tex>, когда из префикса длины и <tex>k</tex> правой части данного правила можно вывести такое, что <tex>wk < \left[i..j|\alpha\right]|</tex>.

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

:Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace \ </tex> и <tex>\forall lbrace k' \mid k' < k \rbrace \ </tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha , i, j+1, k\right] = \:bigvee\limits_{r=i \ldots j+1}\: left(h\left[A \rightarrow \alpha, i, ir, k-1\right] \wedge a\left[\alpha\left[k\right],r, 0j+1\right] = true\right)</tex> — То есть, подстроку <tex>w[i \varepsilonldots j]</tex> можно вывести из префикса длины <tex>k</tex>правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i \ldots r-вывод для 1\right]</tex>, а подстрока <tex>w[r \varepsilonldots j]</tex> выводится из <tex>k</tex>-префиксов правилго символа правой части правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right] </tex>, но на результат это не повлияет, так как в данный момент <tex>a\left[A,i,j+1\right]=false \ </tex>.

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

* '''Завершение''':  : После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>. == Псевдокод ==<code> '''CYK_Modified'''(S, Г): <font color = darkgreen>// S {{---}} строка длины n, Г {{---}} КС-грамматика </font color = darkgreen> '''for''' i = 1..n '''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen> '''if'''( A -> w[i] in Г) a[A, i, i+1] = true <font color = darkgreen>// если в грамматике Г присутствует правило A -> w[i] </font color = darkgreen> '''else''' a[A, i, i+1] = false '''if'''( A -> eps in Г) a[A, i, i] = true <font color = darkgreen>// если в грамматике Г присутствует правило A -> eps </font color = darkgreen> '''else''' a[A, i, i] = false h[A->alpha, i, i, 0] = true '''for''' m = 1..n '''for''' i = 1..n j = i+m '''for''' k = 1..M '''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen> h[A->alpha, i, j+1, k] = OR( for r = i..j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1]) '''for''' i = 1..n '''for''' j = 1..n '''for''' Rj -> alpha a[A, i, j] = OR( for A->alpha) h[A->alpha, i, j, |alpha|] <font color = darkgreen>// где |alpha| {{---}} размер правой части правила</font color = darkgreen> '''return''' a[S, 1, n]  </code>

Расчёт Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.  Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right] \ </tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.  Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</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> памяти. == См. также == * [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]* [[Алгоритм_Эрли|Алгоритм Эрли]]