Теорема Клини: регулярные языки и автоматы

Теорема Клини - центральный факт теории формальных языков: она утверждает, что три на первый взгляд разных способа описать множество строк задают ровно один и тот же класс языков. Регулярное выражение, конечный автомат и сам термин «регулярный язык» оказываются тремя именами одной сущности. Именно поэтому в учебниках их свободно меняют местами: доказав, что язык распознаётся автоматом, вы автоматически знаете, что для него есть регулярное выражение, и наоборот. Ниже разберём, что именно утверждает теорема, как устроены обе стороны её доказательства и почему граница «регулярности» проходит там, где проходит. Чтобы собрать корректный запрос на построение автомата или выражения по своему языку, воспользуйтесь конструктором ниже.

Что утверждает теорема Клини

Теорема Клини связывает три понятия. Регулярные языки - это наименьший класс языков над алфавитом $\Sigma$, замкнутый относительно трёх операций: объединения, конкатенации и итерации (звезды Клини), и содержащий базовые языки - пустое множество $\emptyset$, пустую строку $\{\varepsilon\}$ и одиночные символы $\{a\}$. Регулярные выражения - это синтаксис, который ровно эти операции и записывает. Конечные автоматы - вычислительная модель с конечной памятью, читающая строку слева направо.

Формально утверждение звучит так: язык $L$ распознаётся некоторым конечным автоматом тогда и только тогда, когда он задаётся некоторым регулярным выражением. Связка «тогда и только тогда» означает две теоремы в одной, и доказывать их приходится по отдельности - в обе стороны.

Рассчитать для своей задачи

Три операции, которые порождают всё

Чтобы понять, почему класс называется именно так, удобно начать с конструктивного определения регулярного языка. База - три простейших языка над алфавитом $\Sigma$:

$$\emptyset, \quad \{\varepsilon\}, \quad \{a\} \text{ для каждого } a \in \Sigma.$$

Дальше из уже построенных языков $A$ и $B$ разрешено получать новые тремя операциями:

$$\begin{aligned} A \cup B &= \{\, w : w \in A \text{ или } w \in B \,\}, \\ A \cdot B &= \{\, uv : u \in A,\ v \in B \,\}, \\ A^{*} &= \{\varepsilon\} \cup A \cup AA \cup AAA \cup \dots \end{aligned}$$

Объединение даёт выбор, конкатенация - последовательное сцепление, а звезда Клини - повторение ноль или больше раз. Регулярный язык - это любой язык, который можно собрать из базовых конечным числом применений этих операций. Регулярное выражение - просто текстовая запись такого построения: например, $(ab)^{*}$ задаёт язык всех строк из повторов блока «ab», а $a(a \cup b)^{*}$ - все строки, начинающиеся с $a$.

Сторона первая: от выражения к автомату

Первая половина теоремы Клини строит по любому регулярному выражению эквивалентный автомат. Доказательство идёт индукцией по структуре выражения с помощью конструкции Томпсона: для каждого синтаксического кирпичика есть маленький автомат с эпсилон-переходами, и автоматы собираются друг из друга так же, как выражение собирается из подвыражений.

Для базовых случаев автоматы тривиальны: для $\emptyset$ - два состояния без переходов, для $\{\varepsilon\}$ - переход по пустой строке, для $\{a\}$ - переход по символу $a$. Дальше работают три сборки.

При объединении $A \cup B$ добавляют новое стартовое состояние с двумя эпсилон-переходами в начала автоматов $A$ и $B$. При конкатенации $A \cdot B$ финал автомата $A$ соединяют эпсилон-переходом со стартом $B$. Для итерации $A^{*}$ заворачивают эпсилон-переход с финала обратно на старт и добавляют обход, пропускающий $A$ целиком (это и даёт пустую строку). Так по выражению любой сложности механически собирается недетерминированный конечный автомат.

Рассчитать для своей задачи

Сторона вторая: от автомата к выражению

Обратная половина сложнее: по произвольному конечному автомату нужно построить регулярное выражение, задающее тот же язык. Классический способ - метод исключения состояний. Идея в том, чтобы по очереди выбрасывать промежуточные состояния автомата, перенося информацию о путях через них на метки оставшихся дуг.

Когда выбрасывается состояние $q$, любую пару «вошёл в $q$ - вышел из $q$» заменяют дугой напрямую. Если в $q$ вели дуга с меткой $R$, из $q$ выходила дуга $T$, а сам $q$ имел петлю $S$, то новая прямая дуга получает метку

$$R\,S^{*}\,T,$$

то есть «дойти до $q$, покрутиться в петле сколько угодно раз, выйти из $q$». Метки дуг при этом перестают быть отдельными символами и становятся регулярными выражениями. Исключив все состояния, кроме стартового и финального, мы получаем одну дугу, чья метка и есть искомое регулярное выражение для всего языка. Альтернатива - система уравнений Ардена, где для каждого состояния пишут уравнение на язык достижимых из него строк и решают его, опираясь на лемму $X = SX \cup T \Rightarrow X = S^{*}T$.

Почему обе стороны нужны

Может показаться, что хватило бы одной импликации. Но именно двусторонность делает теорему Клини рабочим инструментом. Доказав замкнутость регулярных языков относительно, скажем, пересечения или дополнения, удобно рассуждать на автоматах (для них конструкция произведения и инверсии финальных состояний очевидна), а итог переводить обратно в выражение. И наоборот: проверить, что конкретный язык регулярен, часто проще, выписав для него короткое регулярное выражение, чем рисуя автомат. Связь с детерминированными автоматами замыкает картину: любой недетерминированный автомат превращается в детерминированный детерминизацией (построением подмножеств), так что и эта модель попадает в тот же класс. Похожая логика «один объект, разные представления» встречается и в смежных моделях - например, в автоматах Мура и Мили, где один распознаватель записывается двумя способами.

Где проходит граница регулярности

Теорема Клини описывает класс ровно, поэтому полезно видеть и его край. Регулярные языки не умеют «считать без ограничений»: язык $\{a^{n}b^{n} : n \geq 0\}$ - строки из $n$ символов $a$, за которыми идёт столько же $b$, - не регулярен, потому что конечная память автомата не может хранить произвольно большое число $n$. Это доказывается леммой о накачке: в достаточно длинной строке регулярного языка есть участок, который можно повторять любое число раз, не выходя из языка. Для $a^{n}b^{n}$ накачка ломает баланс и выводит строку за пределы языка - значит, ни автомата, ни регулярного выражения для него нет. Так теорема Клини задаёт не только что входит в класс, но и косвенно очерчивает, что в него не входит, передавая такие языки следующим уровням иерархии Хомского.

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

• Путают «регулярный язык» с «языком, заданным регулярным выражением в редакторе кода»: программистские regex с обратными ссылками сильнее и выходят за пределы класса теоремы Клини.
• Доказывают только одну импликацию и считают теорему доказанной - нужны обе стороны, конструкция Томпсона и исключение состояний.
• При исключении состояний забывают про петлю $S$ и пишут $RT$ вместо $R\,S^{*}\,T$, теряя все строки, проходящие через состояние больше одного раза.
• Считают, что недетерминированный автомат мощнее детерминированного; по теореме они распознают тот же класс, детерминизация это подтверждает.
• Пытаются построить автомат для $a^{n}b^{n}$ и не понимают, почему не выходит, - язык просто не регулярен, и виновата конечность памяти.

FAQ

Чем регулярное выражение отличается от регулярного языка? Регулярный язык - это само множество строк, а регулярное выражение - конкретная текстовая запись, которая его задаёт. Один и тот же язык можно задать разными выражениями, например $a^{*}$ и $a^{*} \cup \emptyset$.

Зачем в теореме Клини конечный автомат, если есть выражения? Автомат - это вычислительная модель: он подсказывает, как реально распознавать строки за линейное время и как доказывать свойства замкнутости. Выражение удобно записывать, автомат - исполнять.

Все ли языки регулярны? Нет. Регулярные языки - лишь нижний уровень иерархии Хомского. Языки вроде $\{a^{n}b^{n}\}$ или правильных скобочных последовательностей требуют контекстно-свободных грамматик и стека, а не конечной памяти.

Коротко

Теорема Клини доказывает, что регулярные выражения, конечные автоматы и регулярные языки - это три имени одного класса языков, замкнутого относительно объединения, конкатенации и звезды Клини. Прямая сторона строит автомат по выражению (конструкция Томпсона), обратная - выражение по автомату (исключение состояний). Двусторонность позволяет свободно переходить между представлениями, а лемма о накачке очерчивает границу класса: считать неограниченно регулярный язык не умеет.