Изменения

<tex>a_1...a_na</tex> - входная строка. <tex>A_1...A_mA</tex> - нетерминалы.

<tex>S([i,c) j] = true</tex> если есть продукция <tex>A_i \Rightarrow ca_j</tex> (где <tex>c</tex> - терминал).<tex>d[i][,j,k]</tex> - можно ли вывести из нетерминала <tex>A_i</tex> подстроку <tex>a_j...a_k</tex>.Считаем, что <tex>A_0</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 = 1 to m for j = 1 to n d[i][,j,j] = S([i,a[j])

for l = 2 to n for i = 1 to n+1-l for j = 1 to m d[j][,i,i+l-1] = false 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[0,1,n] end