Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть дана грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли э…»)
 
Строка 1: Строка 1:
−
Пусть дана грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
+
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
  
 
== Алгоритм для НФХ-грамматики ==
 
== Алгоритм для НФХ-грамматики ==
−
Пусть <tex>\Gamma</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} = 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, j} =  
 +
\begin{cases}
 +
true,&\text{$A \Rightarrow^{*} w[i..j]$;}\\
 +
false,&\text{else.}
 +
\end{cases}
 +
</tex>.
  
 +
Будем динамически заполненять матрицу <tex>a_{A, i, j}</tex> следующим алгоритмом:
  
−
Базой динамики являются ячейки <tex>a_{A, i, i}</tex>, которые заполняются истиной, если правило <tex>A \rightarrow w[i]</tex> принадлежит грамматике:
+
*'''База'''. Ячейки <tex>a_{A, i, i}</tex> заполняются истиной, если правило <tex>A \rightarrow w[i]</tex> принадлежит множеству правил <tex>P</tex> грамматики <tex>\Gamma</tex>:
 
<tex>a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack</tex>.
 
<tex>a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack</tex>.
  
−
 
+
*'''Переход'''. Пусть на текущем шаге <tex>j-i=m>0</tex>. Если все ячейки, для которых справедливо <tex>j-i<m</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>.
 
<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]]
 
[[Файл: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>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</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>n^2 \cdot |N|</tex> памяти, где <tex>|N|</tex> – количество нетерминалов грамматики.
  
 
Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.
 
Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.

Версия 03:36, 27 февраля 2011

Пусть дана контекстно-свободная грамматика грамматика [math]\Gamma[/math] и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.

Алгоритм для НФХ-грамматики

Пусть [math]\Gamma[/math] приведена к нормальной форме Хомского.

Пусть [math]a_{A, i, j} = true[/math], если из нетерминала [math]A[/math] можно вывести подстроку [math]w[i..j][/math]. Иначе [math]a_{A, i, j} = false[/math]:

[math]a_{A, i, j} = \begin{cases} true,&\text{$A \Rightarrow^{*} w[i..j]$;}\\ false,&\text{else.} \end{cases} [/math].

Будем динамически заполненять матрицу [math]a_{A, i, j}[/math] следующим алгоритмом:

  • База. Ячейки [math]a_{A, i, i}[/math] заполняются истиной, если правило [math]A \rightarrow w[i][/math] принадлежит множеству правил [math]P[/math] грамматики [math]\Gamma[/math]:

[math]a_{A, i, j} = \lbrack A \rightarrow w[i] \in P \rbrack[/math].

  • Переход. Пусть на текущем шаге [math]j-i=m\gt 0[/math]. Если все ячейки, для которых справедливо [math]j-i\lt m[/math], уже вычислены, то алгоритм смотрит, можно ли вывести подстроку [math]w[i..j][/math] из этих ячеек:

[math]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)[/math].

CYK rule.jpg

  • Завершение. После окончания работы ответ содержится в ячейке [math]a_{S, 1, n}[/math], где [math]n = |w|[/math].

Сложность алгоритма

Необходимо вычислить [math]n^2[/math] булевых величин. На каждую требуется затратить [math]n \cdot |P_A|[/math] операций, где [math]|P_A|[/math] – количество правил. Суммируя по всем правилам получаем конечную сложность [math]O \left( n^3 \cdot |\Gamma| \right)[/math].

Алгоритму требуется [math]n^2 \cdot |N|[/math] памяти, где [math]|N|[/math] – количество нетерминалов грамматики.

Минус алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ&oldid=7718»