Что регулярные языки НЕ могут

Соберём в одном месте всё, что регулярки принципиально не умеют, — и поймём, почему за ними начинается мир контекстно-свободных языков.

Регулярный язык распознаётся конечной памятью: автомат помнит лишь одно из конечного числа состояний. Всё, что требует «считать без границы», ему недоступно.

Три классических примера невозможного

1. Сбалансированные скобки. Язык правильных скобочных последовательностей «(()())» не регулярен. Чтобы проверить баланс, нужно помнить, сколько скобок открыто, — а это число неограниченно. Конечный автомат не может хранить произвольный счётчик. Отсюда практический вывод: HTML и вложенные структуры нельзя корректно распарсить регуляркой — знаменитый ответ на StackOverflow про «нельзя парсить HTML регэкспом» именно об этом.

2. aⁿbⁿ. Уже доказали леммой о накачке: нужно сравнить число a с числом b, но автомат не может запомнить n. Это эталон не-регулярного языка.

3. Палиндромы. Язык {ww^R} (строка, за которой следует её разворот) не регулярен: чтобы проверить, что вторая половина зеркальна первой, нужно помнить всю первую половину — а она произвольной длины.

почему скобки не регулярны (накачка):
s = (^p )^p  = ((((...)))) с p парами
|xy| ≤ p ⇒ y состоит только из «(»
накачаем i=2: открывающих больше закрывающих ⇒ не сбалансировано
⇒ противоречие ⇒ язык не регулярен

Что объединяет эти случаи

Во всех трёх примерах нужна память, растущая с длиной входа: счётчик глубины, число символов, копия первой половины. Регулярный язык по определению ограничен конечным числом состояний — конечной памятью. Как только задача требует «помнить произвольно много», регулярок не хватает. Решение — добавить структуру памяти. Стек (магазин) идеально подходит для вложенности: открыли скобку — положили на стек, закрыли — сняли. Так рождается магазинный автомат и класс контекстно-свободных языков. Это ровно следующая ступень иерархии Хомского.

Граница на эксперименте

Покажем разницу: «чётность скобок» (поверхностная проверка, регулярна) против «баланс скобок» (требует стека, не регулярна). Первое реализуется счётчиком по модулю — конечная память. Второе — настоящим стеком.

# баланс скобок: НУЖЕН стек (счётчик глубины)
def balanced(s):
    depth = 0
    for ch in s:
        if ch == "(":
            depth += 1
        elif ch == ")":
            depth -= 1
            if depth < 0:        # закрыли лишнюю
                return False
    return depth == 0            # всё закрыто

# «регулярная» подделка: только чётное число скобок, без баланса
def even_parens(s):
    return s.count("(") % 2 == 0 and s.count(")") % 2 == 0

tests = ["(())", "())(", "(()", "()()"]
for t in tests:
    print(f"{t:>5}: баланс={balanced(t)}  чётность={even_parens(t)}")

Вывод:

 (()): баланс=True  чётность=True
 ())(: баланс=False  чётность=True
  ((): баланс=False  чётность=False
 ()(): баланс=True  чётность=True

Строка «())(» имеет чётное число скобок, но не сбалансирована — её «ловит» только проверка со счётчиком глубины (стеком). Конечный автомат различил бы лишь чётность, но не баланс.

Как работает под капотом

Граница «регулярно / нерегулярно» — это граница «конечная память / неограниченная память». Именно поэтому лексический анализ компилятора (распознавание токенов: идентификаторы, числа, ключевые слова) делают конечными автоматами — там вложенности нет. А вот синтаксический анализ (сопоставление скобок, вложенные выражения, блоки) требует уже КС-грамматики и стека. Разделение лексер/парсер в компиляторах — прямое следствие этой теоретической границы.

Частые ошибки

«Я же написал regex для скобок». Современные «regex» с рекурсивными группами (PCRE `(?R)`) — это уже не регулярные выражения в теоретическом смысле; они вышли за класс регулярных языков именно чтобы справиться с вложенностью.

Путать «чётность» и «баланс». Чётность числа символов регулярна (конечная память), баланс вложенности — нет.

Думать, что длинных строк не бывает. Доказательства про пределы используют сколь угодно длинные строки; на коротких разница незаметна, но язык бесконечен.

Итог

Регулярки не умеют: сбалансированные скобки, aⁿbⁿ, палиндромы — всё, что требует неограниченной памяти.
Причина одна: конечный автомат хранит лишь конечное число состояний и не может считать без границы.
Решение — добавить стек: так появляется магазинный автомат и класс КС-языков.
Практика: лексер (токены) — конечный автомат, парсер (вложенность) — КС-грамматика.