1) Доказательство нерегулярности (лемма о накачке).
Пусть алфавит $\Sigma =\{(,)\}$ и язык
$$L=\{w\in {\Sigma }^{\ast }\mid \text{скобки в}w\text{парные и правильно вложены}\}.$$ Предположим противное, что $L$ регулярен. По лемме о накачке существует константа накачки $p$ такая, что для любого $s\in L$ с $|s|\ge p$ найдётся разбиение $s=xyz$ с условиями $|xy|\le p$, $|y|>0$ и для всех $i\ge 0$ верно $x{y}^{i}z\in L$.
Возьмём строку
\[
s = \underbrace{(((\dots(}_{p}\underbrace{))\dots)}_{p} = '('^{p} )^{p}.
\]
Так как \(|xy|\le p\), подстрока \(y\) состоит только из символа \('('\) и \(y\ne\varepsilon\). Рассмотрим \(i=0\). Тогда строка \(xy^0z\) содержит меньше \('('\) чем \(')'\), значит она не сбалансирована и не принадлежит \(L\). Это противоречит лемме о накачке. Следовательно, \(L\) не регулярный.
2) Контекстно‑свободная грамматика.
Одна простая КС-грамматика, порождающая \(L\):
\[
S \to SS \mid (S) \mid \varepsilon.
\]
Альтернативно эквивалентная форма удобная для LL-парсинга:
\[
S \to (S)S \mid \varepsilon.
\]
Краткое обоснование: правило \((S)S\) позволяет строить любую правильную скобочную последовательность как либо пустую, либо одну корректную пару вокруг корректной последовательности, за которой следует ещё одна корректная последовательность (конкатенация).
3) Алгоритмы парсинга и их сложности.
a) CYK:
- Требуется привести грамматику в Хомском нормальную форму (CNF) — это делается за полиномиальное (на практике линейное по размеру грамматики) время.
- Алгоритм CYK строит таблицу \(T[i,j]\) (подстроки от позиции \(i\) длины \(j\)) и проверяет для каждой пары разбиений, какие нетерминалы могут порождать подстроку. Для длины входа \(n\) время работы стандартно оценивается как
\[
O(n^3)
\]
(точнее $O(n^3\cdot |G|)$ для грамматики размера $|G|$), память $O(n^2)$.
- Подходит для любой КС-грамматики, но для простых скобочных языков не оптимален по времени.
b) Рекурсивный спуск / детерминированный PDA / стековый алгоритм (линейное решение):
- Для грамматики $S\to (S)S\mid \epsilon$ можно написать простой LL(1)-рекурсивный парсер или эквивалентный итеративный алгоритм со стеком:
- Проходя слева направо по входу, при символе \('('\) — положить его в стек; при символе \(')'\) — если стек пуст, отклонить, иначе снять один символ из стека.
- После конца входа принять тогда и только тогда, когда стек пуст.
- Время работы:
$$O(n),$$ память в худшем случае
$$O(n)$$ (глубина стека равна максимальной вложенности).
- Этот алгоритм корректен для языка правильно вложенных скобок и оптимален по времени.
Короткое резюме: язык не регулярный (лемма о накачке), он КС с грамматикой $S\to (S)S\mid \epsilon$, парсится общим CYK за $O(n^3)$ или простым стековым/рекурсивным алгоритмом за $O(n)$.