TM·IX Пределы вычислений Глава 54 из 65
Автоматы и регулярки
Машина, у которой нет ничего, кроме конечного числа состояний. Она проверяет номера телефонов, ищет в гигабайтах журналов и стоит за каждым регулярным выражением. Глава — сборник головоломок: кроссворды из регулярок, турникет, автомат, построенный по формуле, — а в конце разбор аварии, в которой одна регулярка 2 июля 2019 года на 27 минут остановила сайты Cloudflare по всему миру.
Пределы вычислений
- 54 Автоматы вы здесь
- 55 Машина Тьюринга
- 56 Неразрешимое
- 57 P и NP
- 58 Трудные задачи
Опирается на: 07 · Собеседник из строк 19 · Шесть рукопожатий
Что вы унесёте из главы
- писать регулярные выражения для проверки и поиска — классы, повторы, группы, якоря — и пользоваться модулем re
- строить конечный автомат для проверки ввода и переводить недетерминированный автомат в детерминированный
- узнавать регулярки с катастрофическим перебором и переписывать их безопасно
- доказывать леммой о накачке, что задача конечному автомату не по силам
Прошлая глава закончилась вопросом: существует ли программа, которая проверит любую программу на зацикливание? Чтобы ответить, нужно точно сказать, что такое машина, — и начать с простейшей. Простейшая машина помнит одно: в каком она сейчас состоянии. Состояний у неё конечное число, и каждый входной символ переводит её из одного в другое по таблице. Мы встречали такую машину трижды: светофор в главе 31, алгоритм КМП в главе 27, лексер в главе 50. Пора рассмотреть её саму: что она умеет и чего не умеет.
Умеет она, как выяснится, ровно то, что умеют регулярные выражения — короткие формулы вроде \d{2}\.\d{2}\.\d{4}, которыми каждый день проверяют ввод, ищут в журналах и чистят данные. Поэтому глава устроена как сборник головоломок: сначала кроссворды, где вместо определений стоят регулярки, потом автоматы, которые вы построите сами. А в конце — разбор аварии, в которой одна регулярка из одиннадцати символов на 27 минут остановила значительную часть интернета.
Кроссворд первый
Правила простые. В каждую клетку впишите одну букву. Строка, прочитанная слева направо, должна целиком подходить под регулярное выражение своей строки, столбец, прочитанный сверху вниз, — под выражение своего столбца. Регулярное выражение — это образец: буква означает саму себя, а несколько знаков управляют выбором и повторением.
| Запись | Что значит | Пример |
|---|---|---|
К | буква К | КОТ подходит только «КОТ» |
. | любой символ | К.Т: КОТ, КИТ, К5Т |
[КТ] | один символ из перечисленных | [КТ]ОК: КОК, ТОК |
[^Т] | любой символ, кроме перечисленных | [^Т]ОК: КОК, СОК, но не ТОК |
A|B | или A, или B | ДА|НЕТ |
X?, X*, X+ | X ноль или один раз, сколько угодно раз, хотя бы раз | ТО*К: ТК, ТОК, ТООК |
(…) | группа: повторы и «или» действуют на неё целиком | (ОК)+: ОК, ОКОК |
Решая, вы, скорее всего, действовали как машина: читали выражение слева направо и для каждой клетки спрашивали, что сюда можно поставить, помня только, в каком месте выражения находитесь. Так работает и конечный автомат; рассмотрим его поближе.
Машина без памяти
Возьмём турникет в метро. Он бывает в двух состояниях: закрыт и открыт. Событий тоже два: бросили жетон и толкнули. В закрытом состоянии жетон его открывает, а толчок ничего не меняет. В открытом толчок пропускает человека и закрывает турникет, а второй жетон пропадает зря. Вся логика турникета — таблица из четырёх строк.
Турникету неважно, сколько людей прошло за день и сколько жетонов пропало: всё прошлое для него сжато в одно слово, «закрыт» или «открыт». Такое устройство в главе 31 мы назвали конечным автоматом. Теперь опишем его точно. Детерминированный конечный автомат, коротко ДКА, — это пять вещей: конечное множество состояний; алфавит — символы, которые он читает; таблица переходов, которая по состоянию и символу называет следующее состояние; начальное состояние; и множество принимающих состояний. Автомат читает строку символ за символом, двигаясь по таблице, и, дочитав, принимает её, если оказался в принимающем состоянии, а иначе отвергает. «Детерминированный» значит, что на каждом шаге выбора нет: по состоянию и символу следующий шаг определён однозначно.
Множество всех строк, которые автомат принимает, называют его языком. Если считать принимающим состояние «открыт», язык турникета — все последовательности событий, после которых через него можно пройти. Вот автомат поинтереснее: он читает двоичную запись числа, цифру за цифрой, и говорит, делится ли число на три.
Число $2^{64} + 2$ записано 65 цифрами, а автомат обошёлся тремя состояниями. Он не помнит числа — только остаток от деления прочитанного куска на 3. Приписать справа двоичную цифру b — значит умножить число на 2 и прибавить b, а остаток от результата зависит только от прежнего остатка: $(2r + b) \bmod 3$. Это та же мысль, что у КМП: от всего прочитанного нужно помнить одно маленькое число, и тогда памяти хватит на текст любой длины.
Постройте автоматы сами. В редакторе ниже уже лежат турникет и делитель на три, а к ним — несколько заданий.
0-9 — все цифры). Нажмите на подпись перехода, чтобы её изменить или стереть. Внизу строка для проверки: «шаг» читает один символ, «до конца» — всю строку. В заданиях автомат проверяется на наборе строк.Проверка ввода
Самая частая работа конечного автомата в обычной программе — проверить, правильно ли человек что-то ввёл. Возьмём десятичное число, как его пишут в анкете: необязательный минус, цифры, а потом, может быть, точка и ещё цифры. -12.5, 7, 0.25 — да; 12., .5, --3, 1.2.3 — нет. Автомат для этого понадобится из пяти состояний: «ничего не прочитано», «прочитан минус», «идут цифры целой части», «прочитана точка», «идут цифры дробной части». Принимающих два — где число может кончиться.
Автомат и строчка -?[0-9]+(\.[0-9]+)? отвечают одинаково на всех восьми строках, и неслучайно. Прочтите выражение глазами автомата: -? — из старта можно перейти по минусу, а можно и не переходить; [0-9]+ — цифра, а потом петля по цифрам на месте; (\.[0-9]+)? — необязательный хвост: точка, цифра, петля. Обратная косая черта перед точкой нужна потому, что точка без неё значит «любой символ». Функция re.fullmatch из модуля re проверяет, подходит ли под выражение вся строка.
Нервные сети и регулярные события
Главный результат Клини — мост между формулами и машинами. Языки, которые принимают конечные автоматы, называют регулярными, а запись Клини — регулярными выражениями.
Множество строк можно описать регулярным выражением тогда и только тогда, когда его принимает какой-нибудь конечный автомат.
В одну сторону — от выражения к автомату — построение идёт по частям выражения, как разбор из главы 50. Удобно разрешить автомату переходы, которые не читают ни одного символа; их обозначают буквой ε. Каждому кусочку выражения сопоставим автомат с одним входом и одним выходом. Символ — два состояния и стрелка с этим символом. Следование AB — выход автомата для A соединяем ε-стрелкой со входом автомата для B. «Или» A|B — новый вход с ε-стрелками в оба автомата и новый выход, куда ведут ε-стрелки из обоих. Звёздочка A* — ε-стрелка с выхода A обратно на его вход, чтобы повторять, и ε-стрелка с нового входа сразу на новый выход, чтобы не повторять ни разу. Из этих четырёх деталей собирается автомат для любого выражения, и состояний в нём не больше, чем удвоенная длина выражения. Как избавиться от ε-стрелок, покажет следующий раздел.
В другую сторону — от автомата к выражению — состояния выбрасывают по одному, а стрелки, которые шли через выброшенное состояние, заменяют стрелками, подписанными целыми выражениями: если из p в q шли через r, где была петля, то новая стрелка из p в q подписана «путь в r, петля сколько угодно раз, путь из r». Когда останутся только начальное и принимающее состояния, подпись стрелки между ними и есть нужное выражение.
Из теоремы следует практическое правило: всё, что проверяет регулярное выражение без особых добавок, можно проверить, помня конечное количество информации, — и наоборот. Телефонный номер, дата, почтовый индекс, число — регулярные языки. Сбалансированные скобки — нет, и в конце главы мы это докажем.
Машина, которая угадывает
В доказательстве появился странный автомат: у него бывают ε-стрелки и из одного состояния по одному символу может вести несколько стрелок. Запускать его проще всего так, будто он угадывает: на каждой развилке выбирает правильную дорогу, если такая есть. Строка принята, если существует хотя бы один путь, который приводит в принимающее состояние. Такой автомат называют недетерминированным, коротко НКА.
Угадывать машины не умеют, но угадывание можно заменить перебором: вести все варианты сразу. Вместо одного текущего состояния будем хранить множество всех состояний, где автомат может быть. Очередной символ переводит множество в множество. Вот пример, где НКА гораздо проще ДКА: строки из нулей и единиц, в которых третий символ с конца — единица. НКА читает строку, а на какой-то единице «решает», что она третья с конца, и проверяет, что после неё ровно два символа.
У строки 0100 третий символ с конца — единица, и в конце множество содержит принимающее состояние 3; у 0011 там ноль, и состояния 3 в множестве нет. В множестве состояний и спрятано «угадывание»: машина ведёт все догадки сразу. Так же ищет текст метод, который Кен Томпсон описал в 1968 году, и время у него растёт линейно с длиной текста: на каждый символ — один шаг по множеству.
Но ведь множество состояний НКА — тоже состояние, и разных множеств конечное число. Значит, можно заранее построить ДКА, у которого каждое состояние — это множество состояний НКА. Начинаем с множества, где НКА бывает в начале, и для каждого символа вычисляем, куда переходит множество; каждое новое множество — новое состояние ДКА, и для него повторяем то же. Это обход в ширину из главы 19, только вершины графа — множества. Приём называют построением подмножеств; его предложили Майкл Рабин и Дана Скотт в 1959 году в статье, за которую в 1976 году оба получили премию Тьюринга. Из него следует, что угадывание не добавляет силы: всё, что принимает НКА, принимает и какой-нибудь ДКА.
|, *, +, ?, скобки) или выберите набор. Вверху — автомат Томпсона, собранный из деталей доказательства; ε-стрелки пунктирные. Ниже — построение подмножеств по шагам: каждая строка таблицы — новое состояние ДКА, то есть множество состояний НКА. Внизу — получившийся ДКА. Строка для проверки подсвечивает путь в обоих автоматах.Платить за детерминированность приходится размером. У НКА для «третьего символа с конца» четыре состояния, а ДКА должен помнить все три последних символа — иначе, дочитав строку, он не узнает, каким был третий с конца. Проверим, как растёт ДКА, если спрашивать про $n$-й символ с конца.
Каждая лишняя позиция удваивает ДКА: $2^n$ состояний против $n + 1$. Меньше не выйдет: ДКА обязан различать все $2^n$ возможных окончаний строки, ведь для любых двух окончаний найдётся продолжение, после которого одно даёт «да», а другое — «нет». Поэтому программам поиска приходится выбирать из двух путей. Можно построить ДКА заранее и потом читать текст с максимальной скоростью, рискуя взрывом размера, а можно вести множество состояний НКА на лету — медленнее на каждый символ, зато без взрыва. Есть и середина: строить состояния ДКА лениво, только те, что встретились в тексте. Так работают, например, RE2 в Google и регулярки языка Rust.
Томпсон, QED и grep
С тех пор регулярки живут почти везде: в grep и sed, в редакторах кода, в языках от Perl и JavaScript до Python, в базах данных и в правилах межсетевых экранов. Но по дороге их пути разошлись. egrep Альфреда Ахо, вошедший в 1979 году в седьмую редакцию Unix, строил ДКА, как в построении подмножеств. А в 1986 году Генри Спенсер выпустил свободную библиотеку регулярок, которая работала иначе — перебором с возвратом; от неё пошли регулярки Perl, а по их образцу — регулярки большинства языков, включая Python. Почему иначе и чем это кончилось, — в конце главы. Сначала научимся пользоваться тем, что есть.
Регулярки в Python
В Python регулярки — модуль re. Выражение пишут в «сырой» строке r"…": там обратная косая черта остаётся сама собой, а не превращается в спецсимвол строки, как \n. Кроме записей из кроссворда понадобятся ещё несколько. \d — цифра, \w — буква, цифра или подчёркивание, \s — пробельный символ. {n} и {n,m} — повторить ровно $n$ раз или от $n$ до $m$. ^ и $ — начало и конец строки, \b — граница слова. Функций четыре главных: re.fullmatch проверяет строку целиком, re.search ищет первое вхождение, re.findall — все, re.sub заменяет найденное. Круглые скобки не только группируют, но и запоминают: что совпало с группой, можно достать.
Чаще всех в романе упомянут 1812 год, за ним 1805-й — годы двух войн, между которыми идёт действие. re.finditer отдаёт совпадения по одному вместе с группами, а (?P<имя>…) даёт группе имя, по которому её удобно достать. В rf"…" выражение собрано f-строкой, поэтому фигурные скобки повтора пришлось удвоить. И последнее правило, которое экономит часы: re.search ищет образец где угодно в строке, поэтому для проверки ввода нужен re.fullmatch — иначе \d+ «подтвердит», что abc5 — число.
Теперь кроссворды посложнее: в них есть повторы и одна новая запись, о которой — сразу после.
\1 — «то же, что совпало с первой группой»: (.)О\1 подходит под «ТОТ», но не под «ТОК».Шаг за пределы автомата
Запись \1 называется обратной ссылкой: она требует, чтобы дальше снова стоял текст, совпавший с первой группой. С ней легко искать удвоенные слова — частую опечатку «в в» или «что что». В «Войне и мире» удвоения в основном нарочные: так говорят герои.
Удобная запись, но у неё есть цена, и она принципиальная. Язык «слово, повторённое дважды», не регулярен: чтобы проверить, что вторая половина совпадает с первой, нужно помнить первую половину целиком, а она может быть сколь угодно длинной. Конечному автомату такое не по силам; для похожего случая мы докажем это в разделе о накачке. Значит, регулярки Python сильнее выражений Клини, и конечный автомат за ними стоять не может.
Перебор с возвратом
Регулярки Python, Perl, Java и JavaScript не строят автомат. Они пробуют. Встретив выбор — сколько символов отдать x+, какую ветку | взять, — движок берёт первый вариант и идёт дальше. Если дальше не сошлось, он возвращается к последнему выбору и пробует следующий вариант. Это поиск в глубину по дереву вариантов, как обход лабиринта в главе 19 или перебор в главе 9. Обычно дерево маленькое, и всё работает быстро. Но бывают выражения, у которых вариантов, как разрезать строку, экспоненциально много, и если совпадения нет, движок проверит их все до одного.
Каждые два лишних символа — вчетверо дольше: время удваивается с каждым символом. Строку из $n$ иксов можно разрезать на непустые куски примерно $2^n$ способами, и для каждого способа движок проверяет, не стоит ли в конце y. При таком росте строке из сорока иксов понадобились бы многие часы. Это явление называют катастрофическим перебором, а атаку, которая подсовывает серверу такие строки, — ReDoS, отказом в обслуживании через регулярку. Автомату Томпсона та же задача стоит $n$ шагов: множество состояний НКА не растёт от того, сколькими способами можно разрезать строку. В 2007 году Расс Кокс показал разницу на строке из 29 символов и выражении, подобранном для перебора: Perl думал больше минуты, автомат Томпсона — двадцать микросекунд.
Популярные движки устроены так потому, что перебор с возвратом умеет то, чего не умеет автомат: обратные ссылки, «ленивые» повторы, заглядывание вперёд. И на обычных выражениях он быстр. Опасность — в немногих формах: повтор внутри повтора по одним и тем же символам ((x+)+, (a|aa)*), несколько .* подряд и альтернативы, которые могут совпасть с одним и тем же текстом. В лаборатории ниже каждую из этих форм можно испытать.
Разбор аварии: 2 июля 2019
Теперь у нас есть всё, чтобы разобрать аварию, обещанную в начале главы. Её описал в открытом отчёте технический директор Cloudflare Джон Грэм-Камминг, и мы будем идти по этому отчёту. Cloudflare стоит между миллионами сайтов и их посетителями: это сеть доставки содержимого из главы 34 и вдобавок защита от атак. Запросы к сайтам, которые ей доверились, обслуживают одни и те же процессоры, и на них же работает межсетевой экран для веб-приложений — набор правил, которые ищут в запросе признаки атак; многие из них — регулярные выражения.
| Время, UTC | Что произошло |
|---|---|
| 13:42 | Инженер выкатывает новое правило против межсайтовых сценариев (XSS). Правило в режиме «наблюдения»: запросы не блокирует, только отмечает. Но выполнять его всё равно нужно, и по обычному порядку изменение уходит на все серверы мира сразу. |
| 13:45 | Первое предупреждение. Процессоры серверов по всему миру загружены почти на 100 %. Посетители сайтов видят ошибку 502; Cloudflare теряет около 80 % трафика. |
| 14:07 | Межсетевой экран отключён во всём мире. |
| 14:09 | Трафик и загрузка процессоров вернулись к норме. Авария длилась 27 минут. |
| 14:52 | Экран включён снова, уже без нового правила. |
Виновником оказался кусочек правила: .*(?:.*=.*). (?:…) — группа, которая ничего не запоминает, а в остальном это три .* и знак равенства между вторым и третьим. Выражение ищет в тексте «что-нибудь, потом что-нибудь, знак равенства, что-нибудь». Если знака равенства в строке нет, движок перебирает, где начать совпадение, где кончить первое .* и где второе, — три вложенных выбора, порядка $n^3$ шагов. Экспоненты тут нет, «всего лишь» многочлен, но и третьей степени хватило. Повторим в песочнице, а заодно сравним с двумя исправлениями и с автоматом Томпсона из модуля cs.automata.
Правило Cloudflare на каждое удвоение длины дорожает почти в восемь раз, как и положено третьей степени: на строке в две тысячи символов — больше полсекунды, на запросе в несколько килобайт — уже десятки секунд. А запросы приходили тысячами в секунду на каждый сервер. Выражение .*=.* с тем же смыслом растёт лишь квадратично и на тех же строках тратит около миллисекунды. Проверка '=' in s, которой в этой части правила по смыслу и хватило бы, тратит микросекунды. Автомат Томпсона, написанный на чистом Python и потому медленный на каждом символе, растёт линейно: сто тысяч символов для него — доля секунды.
Отчёт идёт дальше регулярки: одна плохая формула стала аварией потому, что сложились несколько причин. Движок регулярок, PCRE, работал перебором с возвратом и не имел защиты от выражения, которое выполняется непомерно долго. Защиту от слишком долгих регулярок, которая была раньше, за несколько недель до того по ошибке убрали при переделке экрана. Порядок выкатки разрешал отправлять правила сразу на весь мир, без пробы на части серверов. И даже режим «наблюдения» выполнял правило. Без любой из этих причин неудачная формула не стала бы аварией.
Среди исправлений, которые Cloudflare объявила в отчёте, — переход на движок RE2 или движок регулярок языка Rust: оба гарантируют время, линейное по длине текста, потому что внутри у них автоматы. Через полвека после статьи Томпсона его метод снова понадобился: с автоматом такая авария невозможна. В самом Python с версии 3.11 есть свои средства: атомарная группа (?>…) и «жадные без возврата» повторы *+, ++ запрещают движку возвращаться внутрь части выражения, которая уже совпала. А правила на каждый день такие: не вкладывайте повторы друг в друга, если они могут съесть одни и те же символы; не ставьте несколько .* подряд; ограничивайте длину того, что проверяете; и проверяйте выражение не только на правильных строках, но и на длинных неправильных — как в задаче о почте ниже.
Чего автомат не может
На второй день экспедиции в главе 50 островитяне заговорили скобками: «ну» открывает, «ти» закрывает, и пары обязаны сходиться. Там же было обещано доказательство того, что конечный автомат такие фразы не проверит. Оставим от языка одни скобки: строки из «(» и «)», в которых каждая скобка закрыта и ни одна не закрыта раньше времени.
Никакой конечный автомат не принимает ровно сбалансированные скобочные строки.
Пусть такой ДКА есть, и состояний у него $p$. Подадим ему $p$ открывающих скобок подряд. До чтения и после каждой из них автомат в каком-то состоянии — всего $p + 1$ моментов, а состояний только $p$. По принципу Дирихле в двух моментах состояние одно и то же: после $i$ и после $j$ открывающих скобок, где $i < j$. Теперь допишем в обоих случаях $i$ закрывающих скобок. Автомат стартует из одного состояния и читает одни и те же символы, значит, закончит тоже в одном состоянии. Но строку из $i$ открывающих и $i$ закрывающих он обязан принять, а строку из $j$ открывающих и $i$ закрывающих — отвергнуть: в ней остались незакрытые скобки. Одно состояние не может быть и принимающим, и нет. Противоречие.
Суть доказательства — в том, что автомат с $p$ состояниями не умеет считать дальше $p$: две разные истории, «открыто $i$» и «открыто $j$», он путает. Тот же приём работает для многих языков, и его оформили в общую лемму. Её первыми доказали Рабин и Скотт в 1959 году, а вскоре заново открыли Иегошуа Бар-Хиллел, Миха Перлес и Эли Шамир.
Для любого регулярного языка $L$ найдётся число $p$ с таким свойством: любую строку $w$ из $L$ длиной не меньше $p$ можно разрезать на три части, $w = xyz$, так что $y$ не пуста, $|xy| \le p$ и все строки $xz$, $xyz$, $xyyz$, $xyyyz$, … тоже лежат в $L$.
Возьмём $p$ равным числу состояний ДКА для $L$. Читая первые $p$ символов $w$, автомат побывает в состояниях $p + 1$ раз, считая начальное, и какое-то повторится: после $x$ и после $xy$ он в одном и том же состоянии. Значит, кусок $y$ ведёт автомат по петле — из состояния в него же. Петлю можно пройти ноль раз, один, два, сколько угодно: после неё автомат окажется там же, дочитает $z$ тем же путём и закончит в том же принимающем состоянии.
Лемму называют леммой о накачке: кусок $y$ можно «накачивать», повторяя. Ею доказывают нерегулярность: если найти в языке длинную строку, которую никак нельзя накачать, не выйдя из языка, — язык не регулярен. Удобно думать об этом как об игре. Противник утверждает, что язык регулярен, и называет $p$. Вы выбираете строку языка длиной не меньше $p$. Противник режет её на $x$, $y$, $z$ по правилам леммы. Вы выбираете, сколько раз повторить $y$. Если получилась строка не из языка — вы выиграли. Если у вас есть способ выиграть при любых ходах противника, язык не регулярен.
Для скобок нужен счётчик, который может расти без предела, а если скобки бывают разных видов — стек, как в главе 15, где мы ими проверяли скобки. Конечный автомат, которому дали стек, называют автоматом с магазинной памятью — стек похож на магазин пистолета: последний вставленный патрон выходит первым. Его языки — контекстно-свободные из главы 50, и рекурсивный спуск, который вы там писали, — тоже такой автомат: стек вызовов Python служит ему стеком.
Лестница машин
Табличку Хомского из главы 50 теперь можно прочесть как лестницу машин, где каждая ступень добавляет памяти. Внизу — конечный автомат: памяти нет, только состояние. Он принимает регулярные языки: числа, даты, телефоны, токены языка программирования. Ступенью выше — автомат со стеком: он считает и проверяет вложенность, его языки — контекстно-свободные, к ним относится синтаксис почти любого языка программирования. Ещё выше — машина с лентой длиной во входную строку, по которой можно ходить туда и обратно и писать; её языки называют контекстно-зависимыми, среди них строки вида «a…a b…b c…c» с равным числом букв. А на самом верху — та же машина, но с бесконечной лентой. Эту лестницу из четырёх ступеней называют иерархией Хомского.
Регулярки Python на эту лестницу не ложатся. С обратными ссылками они проверяют «слово, повторённое дважды», а это не по силам даже автомату со стеком. Зато сбалансированные скобки произвольной глубины модуль re проверить не может. Выходит, слово «регулярное» в названии модуля — дань истории: под капотом у него перебор, и возможности, и опасности у перебора свои.
Чем больше памяти у машины, тем больше языков она распознаёт, — и тем труднее про неё что-либо доказать. Про конечный автомат можно узнать всё: принимает ли он хоть что-нибудь, равны ли два автомата, — для этого есть быстрые алгоритмы. Про машину с бесконечной лентой, как мы скоро увидим, нельзя узнать даже, остановится ли она.
Задачи
Пять задач. Три — регулярки, которые пригодятся завтра: дата, телефон, почта; в каждой спрятан частый подвох. Две — автоматы: запустить ДКА и построить его по НКА.
Напишите parse_date(text): если строка — дата в виде «день.месяц.год», вернуть кортеж трёх целых (день, месяц, год), иначе None. День — от 1 до 31, месяц — от 1 до 12, оба одной или двумя цифрами (1.9.2026 и 01.09.2026 годятся); год — четыре цифры, от 1000 до 2999. Есть ли в феврале 30-е, проверять не нужно: это работа для модуля datetime. Строка должна быть датой целиком — без пробелов и других символов по краям, а цифры — только обычные, от 0 до 9.
Диапазон чисел регулярка описывает перечислением случаев. День: необязательный ноль и цифра от 1 до 9, или 1–2 и любая цифра, или 3 и 0–1: 0?[1-9]|[12][0-9]|3[01]. Месяц устроен так же, только короче. Не забудьте взять «или» в скобки: без них | разрежет всё выражение пополам.
Заготовка спотыкается дважды, даже если поправить числа. re.match с $ принимает '1.1.2000\n': в Python $ совпадает и перед переводом строки в самом конце. Проверяйте всю строку через re.fullmatch. А \d в Python означает любую цифру Юникода, в том числе арабско-индийские ٢٠٢٤, — пишите [0-9].
Выражение компилируется один раз, re.compile, а проверяется много: так быстрее и нагляднее. Обе ловушки из второй подсказки встречаются в жизни: из-за $ перед переводом строки в журналах и формах проходят строки с хвостом, а \d пропускает цифры, которые потом по-разному поймут разные части программы. Проверку «бывает ли 31 апреля» регулярке лучше не поручать: datetime.date(year, month, day) бросит исключение сам.
Люди пишут телефоны как попало: +7 (912) 345-67-89, 8 912 345 67 89, 89123456789. Напишите normalize_phone(text), которая приводит правильный номер к виду +79123456789, а неправильный отвергает, возвращая None. Правильный номер — это код страны (+7, 7 или 8), потом трёхзначный код, возможно в круглых скобках, и семь цифр номера — подряд или группами по три, две и две, как 345-67-89 и 345-6789. Между группами может стоять один пробел или один дефис, а может ничего. Других символов в строке быть не должно.
Заготовка выбрасывает всё, кроме цифр, и поэтому принимает мусор: +7 (912 345-67-89 с незакрытой скобкой, тел. 89123456789, +8 912…. Опишите форму номера полностью и проверяйте re.fullmatch.
Код в скобках или без — это «или» двух вариантов: (?:\(([0-9]{3})\)|([0-9]{3})). Совпадёт только одна из двух групп, вторая будет None, поэтому код достают как m.group(1) or m.group(2). Необязательный разделитель — [ -]?.
Со скобками вокруг кода регулярка справляется, хотя «скобки автомату не по силам»: здесь пара всего одна, глубина вложенности ограничена, и автомату достаточно помнить, открыта ли она. Невозможным становится только произвольная глубина. А семь цифр подряд и 345-6789 выражение принимает потому, что разделители необязательны, — группы по 3, 2 и 2 цифры стоят вплотную.
Проверка адреса почты из заготовки отвечает правильно на всех обычных строках. Но на одной длинной строке без @ она думает дольше, чем живёт сервер. Исправьте PATTERN так, чтобы is_email отвечала так же и на любой строке длиной в десятки тысяч символов успевала за доли секунды. Правила адреса: имя — слова из латинских букв и цифр, разделённые одной точкой, дефисом или подчёркиванием (разделитель не может стоять в начале, в конце и дважды подряд); потом @; потом домен — части из латинских букв, цифр и дефисов (дефис не в начале и не в конце части), разделённые точками, не меньше двух частей, последняя — только буквы, не короче двух.
Запустите тесты: правильность пройдёт, а на строке из сорока букв a и восклицательного знака проверка не уложится в отведённое время. Виновата первая группа: ([A-Za-z0-9]+[._-]?)* — повтор внутри повтора, и разделитель в нём необязателен. Строку aaaa эта группа может разрезать на куски $2^{n-1}$ способами — как (x+x+)+ в разделе о переборе.
Сделайте так, чтобы каждый кусок строки можно было отнести к выражению только одним способом. Пусть каждый повтор начинается с обязательного разделителя: слово, а потом сколько угодно раз «разделитель и слово». Домен в заготовке уже записан так.
Язык не изменился, изменилась однозначность. В {WORD}(?:[._-]{WORD})* каждая итерация повтора обязана начаться с разделителя, поэтому, глядя на строку, ясно, где кончается одно слово и начинается следующее: возвращаться и пробовать другой разрез незачем. Такое выражение работает за время, близкое к линейному, хотя движок по-прежнему перебирает с возвратом. Тот же приём — убрать неоднозначность — спас бы и правило Cloudflare. Реальные адреса почты устроены сложнее (в имени бывают +, кавычки и даже пробелы), поэтому на практике адрес проверяют простым выражением, а потом отправляют на него письмо со ссылкой.
Автомат задан словарём: "start" — начальное состояние, "accept" — множество принимающих, "delta" — переходы {(состояние, символ): состояние}. Например, турникет: {"start": "закрыт", "accept": {"открыт"}, "delta": {("закрыт", "ж"): "открыт", …}}. Напишите две функции. run_dfa(dfa, text) возвращает True, если автомат принимает строку; если на каком-то символе перехода нет, строка отвергнута. divisible_dfa(k) строит в том же формате автомат над символами "0" и "1", который принимает двоичные записи чисел, делящихся на k (ведущие нули разрешены, пустая строка — это 0), и в котором не больше k состояний. В тестах есть число из 317 тысяч двоичных цифр.
dfa["delta"][(state, ch)] бросает KeyError, если перехода нет, а нужно ответить «не принята». Словарный метод .get вернёт None — и тогда можно сразу вернуть False.
Для делимости вспомните автомат «на три» из раздела «Машина без памяти»: состояние — остаток прочитанного числа, приписанная справа цифра b переводит остаток r в (2 * r + b) % k. Состояния — числа от 0 до k - 1, начальное и единственное принимающее — 0.
Таблица переходов — словарь, и шаг автомата стоит одного обращения к нему, поэтому 317 тысяч цифр читаются за доли секунды: время линейно, а память не растёт вовсе. Отсутствующий переход в таблице — обычный способ сказать «дальше дороги нет»: в учебниках вместо него рисуют лишнее «мёртвое» состояние, из которого не выйти, а в программах его не хранят. Остатков ровно k, и меньше бывает только для особых k: например, для чётных, начиная с 4, часть состояний можно склеить. Найти самый маленький автомат для данного языка умеет алгоритм минимизации — ещё одно, что про конечные автоматы можно узнать быстро.
Напишите to_dfa(nfa) — построение подмножеств. НКА задан словарём: "start", "accept" — множество принимающих, "delta" — {(состояние, символ): множество состояний} и, может быть, "eps" — ε-переходы {состояние: множество состояний}. Вернуть ДКА в формате задачи «Запустить автомат», где каждое состояние — frozenset состояний НКА. Начальное состояние ДКА — все состояния, куда НКА попадает из начального по ε-переходам (включая само начальное). В ДКА должны быть только состояния, достижимые из начального, и ни одного перехода в пустое множество. Алфавит — символы, которые встречаются в "delta". Тесты сравнивают ваш ДКА с НКА на сотнях строк и строят ДКА на 4096 состояний.
Заготовка верна для НКА без ε-переходов — первый тест она проходит. Не хватает одного: после каждого шага, и до первого шага тоже, нужно добавить к множеству всё, куда из него можно попасть по ε. Это ε-замыкание.
ε-замыкание — обход графа ε-переходов из всех состояний множества сразу, как обход в глубину из главы 19: стек, множество посещённых, пока стек не пуст — снять состояние и положить его непосещённых соседей. Верните frozenset, чтобы множество можно было класть в другое множество и использовать как ключ словаря.
Очередь на list.pop(0) на 4096 состояниях ещё успевает, но каждое такое снятие сдвигает весь список; collections.deque из главы 15 снимает с начала за $O(1)$.
Два обхода вложены друг в друга: внешний, в ширину, идёт по состояниям ДКА, внутренний, в глубину, считает ε-замыкание. Принимающими становятся все множества, где есть хоть одно принимающее состояние НКА: «хотя бы одна догадка привела к успеху». Для автомата из тестов — НКА Томпсона для (a|b)*abb с одиннадцатью состояниями — получается пять состояний, а начальное — {0, 1, 2, 4, 7}: столько мест, где НКА может стоять, не прочитав ни одной буквы. Если запустить to_dfa, а потом run_dfa из прошлой задачи, получится работающий движок регулярок без перебора — как egrep 1979 года.
Куда дальше
Конечный автомат оказался машиной, про которую можно узнать всё и которая умеет немного. Он не сосчитает скобки и не сравнит две половины строки: всё прошлое у него сжато в одно из конечного числа состояний. Стек помог со скобками, но и у стека есть предел. Со стеком нельзя проверить строки вида «a…a b…b c…c» с равным числом букв: чтобы сравнить «a» с «b», их приходится снимать со стека, и для сравнения с «c» ничего не остаётся.
Что, если дать автомату память без всяких ограничений? Пусть у него будет бесконечная лента из клеток и головка, которая читает клетку, пишет в неё символ и сдвигается на шаг вправо или влево. Таблица переходов почти та же, что у турникета: по состоянию и прочитанному символу — что написать, куда сдвинуться и в какое состояние перейти. В 1936 году такую машину придумал 23-летний Алан Тьюринг и утверждал, что она умеет всё, что вообще можно вычислить по правилам: всё, что умеют Python, «Искра-8» и человек с карандашом и бесконечной тетрадкой. О ней — следующая глава. А через одну мы вернёмся к вопросу, с которого начали эту: можно ли узнать, остановится ли такая машина.