54
правки
Изменения
м
→Псевдокод
<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_0A_1</tex> - стартовый нетерминал.
function CYK (a: array [1..n] of char, P: array [1..m,1..m,1..m] of bool, S: array []) : bool
for k = i to i+j-2
d[j,i,i+l-1] = d[j,i,i+l-1] or (d[j,i,k] and d[j,k+1,i+l-1])
result = d[01,1,n]
end
