418
правок
Изменения
м
→Асимптотика
Следовательно, общее время работы алгоритма {{---}} <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> {{---}} количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
== Пример работы ==
Дана грамматика [[Правильные_скобочные_последовательности|правильных скобочных последовательностей]] <tex>\Gamma</tex>:
<tex>\begin{array}{l l}
A \rightarrow \varepsilon|BC\\
D \rightarrow BC\\
B \rightarrow (\\
C \rightarrow )|DE\\
E \rightarrow )\\
\end{array}</tex>
Дано слово <tex>w = $()(())$</tex>.
== См. также ==
