Значение <tex>d[S,1,n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике.
Очевидно, что алгоритм работает за время <tex>O(n^3)</tex> (где <tex>n</tex> - длина строки) и требует <tex>O(n^2)</tex> памяти (обе оценки с точностью до константных множителей, зависящих от конкретной грамматики).
Заметим, что если массив будет хранить целые числа, а формулу динамики заменить на <tex>d[A,i,j] = \sum\limits_{A \Rightarrow BC}\sum\limits_{k = i}^{j-1} d[B,i,k] \cdot d[C,k+1,j]</tex>, то <tex>d[A,i,j]</tex> - количество способов получить подстроку <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
=== Сложность алгоритма ===
Пусть, <tex>n<tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
=== Псевдокод ===
<tex> funtion CYK (a</tex> - входная строка. <tex>A</tex> длины n, G - нетерминалы.<tex>P[iнабор правил вывода грамматики с m нетерминалами,j,k] = true</tex> если есть продукция <tex>A_i \Rightarrow A_j A_k</tex>.<tex>S[i,j] = true</tex> если есть продукция <tex>A_i \Rightarrow a_j</tex>.<tex>d[i,j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.Считаем, что <tex>A_1</tex> - стартовый нетерминал. function CYK (a: array [1..n] of char, P: array [1..m,1..m,1..m] of bool, S: array []) : bool var d: array [1..m,1..n,1..n] of -> bool
begin
for i = d : array [1 to ..m,1..n,1..n] of bool for j i = 1 to n if (A -> a[i] - правило грамматики) d[A,i,j,ji] = S[i,j]true for l = 2 1 to n-1 for i = 1 to n+1-l for j = 1 to m d[j,i,i+l(A -> BC -1] = falseправило грамматики) for k = i to i+jl-21 d[jA,i,i+l-1] = d[jA,i,i+l-1] or (d[jB,i,k] and d[jC,k+1,i+l-1]) result = d[1S,1,n]
end
