418
правок
Изменения
Нет описания правки
{{Задача|definition = Пусть дана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] грамматика <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_{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>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
Обработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>.
Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>.
Недостаток алгоритма заключается в том, что изначально грамматику необходимо привести к НФХ.
== См. также ==
==Источники информации==
