Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Более подробное описание)
Строка 4: Строка 4:
  
 
== Алгоритм для произвольной грамматики ==
 
== Алгоритм для произвольной грамматики ==
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.
+
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.
  
Введём вспомогательную динамику: <tex>h_{A \rightarrow \alpha, i, j, k} = \left[\alpha\left[1..k\right] \Rightarrow^* w\left[i..j\right]\right] \quad \left(\forall A \rightarrow \alpha \in \Gamma, k \le M\right)</tex> — можно ли из префикса длины <tex>k</tex> правой части данного правила вывести <tex>w\left[i..j\right]</tex>. Также введём динамику <tex>a_{A,i,j} = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично базовой версии алгоритма.
+
Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j]\right]</tex>, аналогично базовой версии алгоритма.
  
* '''База динамики''': <tex>a_{A, i, i} = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>a_{A, i, i-1} = \left[ A \rightarrow \varepsilon \right]</tex> <tex>\varepsilon</tex>-вывод; <tex>\forall A \rightarrow \alpha \:\: h_{A \rightarrow \alpha, i, i-1, 0} = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов правил.
+
Также введём вспомогательный трехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true</tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..j\right]</tex>.  
  
* '''Переход''': Пусть для всех подстрок <tex>w[i..j]</tex> динамики уже вычислены. Сначала вычислим вспомогательную динамику: <tex>\forall k: h_{A \rightarrow \alpha, i, j, k} = \bigvee\limits_{r=i-1..j}\left(h_{A \rightarrow \alpha, i, r, k-1} \wedge a_{\alpha[k],r+1,j}\right)</tex>. Это вычисление может обратится к <tex>a_{A,i,j}</tex>, но на результат это не повлияет, так так в данный момент <tex>a_{A,i,j}=false</tex>. Главная динамика выражается так: <tex>a_{A,i,j}=\bigvee\limits_{A \rightarrow \alpha}h_{A \rightarrow \alpha, i, j, \left|\alpha\right|}</tex>.
+
* '''База динамики''': <tex>a\left[A, i, i\right] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>, иначе  <tex>a\left[A, i, i\right] = false</tex>. <tex>a\left[A, i, i\right] = \left[ A \rightarrow w[i] \in P \right]</tex> — вывод терминалов, <tex>a\left[A, i, i-1\right] = \left[ A \rightarrow \varepsilon \right]</tex> <tex>\varepsilon</tex>-вывод; <tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i-1, 0\right] = true</tex> — <tex>\varepsilon</tex>-вывод для <tex>\varepsilon</tex>-префиксов правил.
  
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.
+
* '''Переход''': Пусть для всех подстрок <tex>w[i..j]</tex> динамики уже вычислены. Сначала вычислим вспомогательную динамику: <tex>\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i-1..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j\right]\right)</tex>. Это вычисление может обратится к <tex>a\left[A,i,j\right]</tex>, но на результат это не повлияет, так так в данный момент <tex>a\left[A,i,j\right]=false</tex>. Главная динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right]</tex>.
 +
 
 +
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.
  
 
== Оценка сложности ==
 
== Оценка сложности ==

Версия 14:53, 17 января 2017

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

Базовая версия данного алгоритма работает только для грамматик в нормальной форме Хомского. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках без цепных правил и без [math]\varepsilon[/math]-правил.

Алгоритм для произвольной грамматики

Обозначим [math]M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|[/math] — максимальную длину правой части правила.

Будем решать задачу динамическим программированием. Введём динамику [math]a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j]\right][/math], аналогично базовой версии алгоритма.

Также введём вспомогательный трехмерный массив [math]h\left[A \rightarrow \alpha, i, j, k\right] = true[/math] тогда и только тогда, когда из префикса длины [math]k[/math] правой части данного правила можно вывести [math]w\left[i..j\right][/math].

  • База динамики: [math]a\left[A, i, i\right] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math], иначе [math]a\left[A, i, i\right] = false[/math]. [math]a\left[A, i, i\right] = \left[ A \rightarrow w[i] \in P \right][/math] — вывод терминалов, [math]a\left[A, i, i-1\right] = \left[ A \rightarrow \varepsilon \right][/math][math]\varepsilon[/math]-вывод; [math]\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i-1, 0\right] = true[/math][math]\varepsilon[/math]-вывод для [math]\varepsilon[/math]-префиксов правил.
  • Переход: Пусть для всех подстрок [math]w[i..j][/math] динамики уже вычислены. Сначала вычислим вспомогательную динамику: [math]\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i-1..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j\right]\right)[/math]. Это вычисление может обратится к [math]a\left[A,i,j\right][/math], но на результат это не повлияет, так так в данный момент [math]a\left[A,i,j\right]=false[/math]. Главная динамика выражается так: [math]a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right][/math].
  • Завершение: После окончания работы ответ содержится в ячейке [math]a\left[S, 1, n\right][/math], где [math]n = |w|[/math].

Оценка сложности

Расчёт вспомогательной динамики занимает [math]O \left( n^3 \cdot |\Gamma| \cdot M \right)[/math] времени, основной динамики — [math]O \left( n^2 \cdot |\Gamma| \right)[/math]. Итоговая временная сложность алгоритма равна [math]O \left( n^3 \cdot |\Gamma| \cdot M \right)[/math]. Алгоритму требуется [math]O(n^2 \cdot |\Gamma| \cdot M)[/math] памяти.