390
правок
Изменения
Исправил многоточия
== Алгоритм для произвольной грамматики ==
Будем решать задачу динамическим программированием. Введём динамику <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>\lbrace \langle j, i \rangle \mid j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>, и <tex>k</tex> такое, что <tex>k < \left|\alpha\right|</tex>.
* '''Переход''':
:Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace \ </tex> и <tex>\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, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)</tex> То есть, подстроку <tex>w[i..\ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..\ldots r-1\right]</tex>, а подстрока <tex>w[r..\ldots 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>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..\ldots r-1\right] \ </tex>, а подстрока <tex>w[r..\ldots j]</tex> выводится, если <tex>w\left[r..\ldots j\right]=\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>.
* '''Завершение''':
<code>
'''CYK_Modified'''(S, Г): <font color = darkgreen>// S {{---}} строка длины n, Г {{---}} КС-грамматика </font color = darkgreen>
'''for''' i = 1..\ldots 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] = false
h[A->alpha, i, i, 0] = true
'''for''' m = 1..\ldots n '''for''' i = 1..\ldots n
j = i+m
'''for''' k = 1..\ldots M
'''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen>
h[A->alpha, i, j+1, k] = OR( for r = i..\ldots j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1]) '''for''' i = 1..\ldots n '''for''' j = 1..\ldots 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>
