Изменения
→Алгоритм для произвольной грамматики
:После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.
== Псевдокод ==
<code>
дано строка S из n символов: a1 ... an.
дано грамматика
дан массив a[A,i,j] булевских значений, инициализированных значениями Ложь.
дан массив h[A -> alpha, i, j, k] булевских значений, инициализированных значениями Ложь.
для каждого i = 1 : n
для каждой продукции Rj -> ai
присвоить P[1,i,j] = Истина
для каждого i = 2 : n -- длина интервала
для каждого j = 1 : n-i+1 -- начало интервала
для каждого k = 1 : i-1 -- разбиение интервала
для каждой продукции RA -> RB RC
если P[k,j,B] и P[i-k,j+k,C]
то присвоить P[i,j,A] = Истина
если для некоторого x из множества s P[n,1,x] = Истина, где s все индексы Rs
то возвратить S принадлежит языку
иначе возвратить S не принадлежит языку
</code>
== Оценка сложности ==
