Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
</tex>.
Будем динамически заполнять матрицу <tex>a_{A, i, j}</tex> следующим алгоритмом (индукция по <tex>m= j - i</tex>):
*'''База'''. <tex>m = 0</tex>. Ячейки <tex>a_{A, i, i}</tex> заполняются истинойзначением <tex>true</tex>, если правило <tex>A \rightarrow w[i]</tex> принадлежит множеству правил <tex>P</tex> грамматики <tex>\Gamma</tex>:<tex>a_{A, i, i} = \lbrack A \rightarrow w[i] \in P \rbrack</tex>.
*'''Переход'''. Пусть на текущем шаге Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m>0\rbrace</tex>. Если все ячейки, Значения для которых справедливо всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j-i<m\rbrace</tex>, уже вычислены, то алгоритм смотрит, можно ли вывести подстроку <tex>w[i..j]</tex> из этих ячеектак что:<tex>a_{A, i, j} = \bigvee\limits_{k=i}^{j-1} \bigvee\limits_{A \rightarrow BC} \left( a_{B, i, k} \wedge a_{C, k+1, j} \right)</tex>.
[[Файл:CYK_rule_2.jpg]]
Необходимо вычислить <tex>n^2</tex> булевых величин. На каждую требуется затратить <tex>n \cdot |P_A|</tex> операций, где <tex>|P_A|</tex> – количество правил. Суммируя по всем правилам получаем конечную сложность <tex>O \left( n^3 \cdot |\Gamma| \right)</tex>.
Алгоритму требуется <tex>n^2 \cdot |N|</tex> памяти, где <tex>|N|</tex> – — количество нетерминалов грамматики.
