17
правок
Изменения
Новая страница: «Пусть дана грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли э…»
Пусть дана грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
== Алгоритм для НФХ-грамматики ==
Пусть <tex>\Gamma</tex> приведена к НФХ.
Представим <tex>a_{A, i, j} = true</tex>, если можно из <tex>A</tex> вывести подстроку <tex>w[i..j]</tex>. Иначе <tex>a_{A, i, j} = false</tex>.
<tex>a_{A, i, j} = \lbrack A \Rightarrow^{*} w[i..j] \rbrack</tex>.
Базой динамики являются ячейки <tex>a_{A, i, i}</tex>, которые заполняются истиной, если правило <tex>A \rightarrow w[i]</tex> принадлежит грамматике:
<tex>a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack</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.jpg]]
Пусть на текущем шаге <tex>j-i=k</tex>. Тогда мы смотрим, можно ли вывести подстроку <tex>w[i..j]</tex> из ячеек матрицы, для которых <tex>j-i<k</tex> и <tex>A \rightarrow BC</tex>.
По окончанию динамики ответ будет содержаться в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.
== Сложность алгоритма ==
Необходимо вычислить <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> – количество нетерминалов грамматики.
Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.
== Алгоритм для НФХ-грамматики ==
Пусть <tex>\Gamma</tex> приведена к НФХ.
Представим <tex>a_{A, i, j} = true</tex>, если можно из <tex>A</tex> вывести подстроку <tex>w[i..j]</tex>. Иначе <tex>a_{A, i, j} = false</tex>.
<tex>a_{A, i, j} = \lbrack A \Rightarrow^{*} w[i..j] \rbrack</tex>.
Базой динамики являются ячейки <tex>a_{A, i, i}</tex>, которые заполняются истиной, если правило <tex>A \rightarrow w[i]</tex> принадлежит грамматике:
<tex>a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack</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.jpg]]
Пусть на текущем шаге <tex>j-i=k</tex>. Тогда мы смотрим, можно ли вывести подстроку <tex>w[i..j]</tex> из ячеек матрицы, для которых <tex>j-i<k</tex> и <tex>A \rightarrow BC</tex>.
По окончанию динамики ответ будет содержаться в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.
== Сложность алгоритма ==
Необходимо вычислить <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> – количество нетерминалов грамматики.
Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.
