54
правки
Изменения
м
Нет описания правки
Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом:
* <tex> S → \Rightarrow (S) → \Rightarrow (SS) → \Rightarrow (()(S)) → \Rightarrow (()(()))</tex>
== Нормальная форма Хомского ==
Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
Обработка правил вида <tex>A \Rightarrow rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>.
