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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
 
Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <tex>\Gamma</tex> и слово <tex>w \in \Sigma^{*}</tex>. Требуется выяснить, выводится ли это слово в данной грамматике.
  
[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках.
+
[[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|Базовая версия]] данного алгоритма работает только для грамматик в [[нормальная форма Хомского|нормальной форме Хомского]]. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. В отличии от базовой версии, нам не важны [[Удаление_цепных_правил_из_грамматики|цепные правила]] и [[Удаление_eps-правил_из_грамматики|<tex>\varepsilon</tex>-правила]].
  
 
== Алгоритм для произвольной грамматики ==
 
== Алгоритм для произвольной грамматики ==
Строка 19: Строка 19:
 
<tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i, 0\right] = true</tex>.
 
<tex>\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i, 0\right] = true</tex>.
  
* '''Переход''': Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> и <tex>\lbrace k' | k' < k \rbrace</tex> уже вычислены, поэтому вспомогательная динамика: <tex>\forall k: h\left[A \rightarrow \alpha, i, j, k\right] = \bigvee\limits_{r=i..j}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha[k],r+1,j+1\right]\right)</tex>. Это вычисление может обратится к <tex>a\left[A,i,j\right]</tex>, но на результат это не повлияет, так так в данный момент <tex>a\left[A,i,j\right]=false</tex>.  
+
* '''Переход''': Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> и <tex>\lbrace k' | k' < k \rbrace</tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i..j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha,r,j+1\right]\right)</tex>. То есть, подстроку <tex>w[i \dots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>, а подстрока <tex>w[r \dots j]</tex> выводится из правой части данного правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\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[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right]</tex>. То есть, подстроку <tex>w[i \dots j-1]</tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>,
  
 
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.
 
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a\left[S, 1, n\right]</tex>, где <tex>n = |w|</tex>.

Версия 19:34, 17 января 2017

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

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

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

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

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

Рассмотрим все тройки [math]\lbrace \langle j, i \rangle | j-i=m \rbrace[/math], где [math]m[/math] — константа и [math]m \lt n[/math], и [math]k[/math] такое, что [math]k \lt \left|\alpha\right|[/math].

  • База динамики:

[math]a\left[A, i, i+1\right] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math], иначе [math]a\left[A, i, i+1\right] = false[/math];

[math]a\left[A, i, i\right] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow \varepsilon[/math], иначе [math]a\left[A, i, i\right] = false[/math];

[math]\forall A \rightarrow \alpha \:\: h\left[A \rightarrow \alpha, i, i, 0\right] = true[/math].

  • Переход: Пусть значения для всех нетерминалов, пар [math]\lbrace \langle j', i' \rangle | j' - i' \lt m \rbrace[/math] и [math]\lbrace k' | k' \lt k \rbrace[/math] уже вычислены, поэтому вспомогательная динамика: [math] h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i..j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha,r,j+1\right]\right)[/math]. То есть, подстроку [math]w[i \dots j][/math] можно вывести из префикса длины [math]k[/math] правой части данного правила, если из префикса длины [math]k-1[/math] правой части данного правила можно вывести [math]w\left[i..j-1\right][/math], а подстрока [math]w[r \dots j][/math] выводится из правой части данного правила. Это вычисление может обратится к [math]a\left[A,i,j+1\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]w[i \dots j-1][/math] можно вывести из нетерминала [math]A[/math], если из длины правой части данного правила можно вывести [math]w\left[i..j-1\right][/math],

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

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

Обозначим [math]M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|[/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] памяти.