Лемма о разрастании (Pumping Lemma): Математика пределов регулярных выражений
Регулярные выражения (Regex) — невероятно мощный инструмент для парсинга текста. Разработчики используют их для проверки email-адресов, номеров кредитных карт и телефонных кодов. Однако у них есть фундаментальный математический изъян: конечные автоматы, стоящие за регулярными выражениями, "не умеют считать". Как строго доказать, что какую-то строку невозможно распарсить с помощью Regex? Для этого в дискретной математике создана Лемма о разрастании (Pumping Lemma).
Классический пример задачи, непосильной для Regex: парсинг вложенных круглых скобок в математическом выражении (или тегов в HTML). Язык, состоящий из N открывающих скобок, за которыми следует ровно N закрывающих скобок (где N — любое число), обозначается как L = { a^n b^n }. Интуитивно понятно, что конечному автомату не хватит состояний (памяти), чтобы "запомнить", сколько именно скобок он открыл, если N может быть бесконечно большим. Но интуиция — не доказательство.
Лемма о разрастании (Pumping Lemma) дает строгий математический критерий. Она гласит: если язык является регулярным, то любая достаточно длинная строка S из этого языка (длина которой больше числа состояний автомата p) может быть разбита на три части: S = x*y*z. При этом выполняются три условия:
- Длина средней части y больше нуля (y не пустая).
- Длина начала и середины (x и y вместе) не превышает p.
- Самое главное (Разрастание): Если мы возьмем эту среднюю часть y и повторим (накачаем) ее любое количество раз (0, 1, 2, 3...), полученная новая строка обязательно должна остаться принадлежать нашему языку! Формально:
x * y^k * z ∈ Lдля любого k ≥ 0.
Доказательство основано на принципе Дирихле (Pigeonhole principle). Если длина строки больше числа состояний конечного автомата, значит, при ее чтении автомат неизбежно посетит хотя бы одно состояние дважды. Это означает, что в графе автомата есть цикл. Цикл соответствует части строки y. И раз есть цикл, мы можем пройти по нему сколько угодно раз (накачать y), и автомат всё равно в итоге придет в допускающее конечное состояние.
Применяя Лемму от противного к языку a^n b^n, мы берем строку из N букв a и N букв b. По лемме часть y обязана состоять только из букв a. Если мы "накачаем" (удвоим) часть y, в новой строке букв a станет больше, чем букв b. Баланс скобок нарушится, новая строка не будет принадлежать языку. Противоречие! Значит, исходное предположение неверно, и язык скобок математически не является регулярным. Именно поэтому для парсинга HTML или JSON нельзя использовать одни лишь регулярные выражения; для этого требуются контекстно-свободные грамматики и стековые анализаторы.
