2.4. Теорема Клини

Теперь докажем, что семейства регулярных и представимых языков совпадают.

Теорема 2.9. Язык представим тогда и только тогда, когда он регулярен.

Доказательство. В силу леммы 2.6 достаточно доказать, что каждый представимый язык регулярен. По лемме 2.3 для этого достаточно доказать, что каждый язык, представимый конечным детерминированным автоматом, регулярен.

Предположим, что L = L(G), где G - конечный детерминированный автомат с n вершинами q₁, ..., q_n, n≥1, и начальной вершиной q₁. Через L(i, j, k), где 1≤i≤n, 1≤j≤n и 1≤k≤n, обозначим семейство помечающих слов всех таких путей в G из q_i в q_j, которые не проходят ни через одну вершину q_t, где t>k (из определения ясно, что λ∈ L (i, j, k), точности тогда, когда i = j).

Для всех i и j язык L (i, j, 0) либо пуст, либо представляет собой объединение некоторых из языков {λ} и {a}, где a пробегает алфавит языка L(G). Следовательно, для любых i и j язык L(i, j, 0) регулярен. (Заметим, что {λ} обозначается регулярным выражением ∅^∧*.)

Продолжая индукцию по k, предположим, что для фиксированного k, 0≤k≤n-1, каждый язык L(i, j, k) регулярен. Очевидно, что для любых i и j

откуда мы заключаем, что каждый язык L(i, j, k+1) регулярен. Следовательно, по индукции каждый язык L(i, j, n) также регулярен.

Но язык L = L(G) представляет собой объединение языков L(i, j, n), таких, что q₁, является заключительной вершиной G; поэтому язык L регулярен. □

Еще раз отметим, что все рассуждения, проведенные в доказательстве теоремы 2.9, конструктивны: если дано регулярное выражение для языка L, то можно построить конечный (или конечный детерминированный) автомат, представляющий L, и обратно. Таким образом, в силу теоремы 2.8 существует алгоритм, устанавливающий, задают ли два данных регулярных выражения один и тот же язык. Мы хотим подчеркнуть, что алгоритмы, вытекающие из приведенных выше доказательств, не являются самыми практичными. В конкретных ситуациях специфические соображения или алгоритмы, приведенные, например, в [Sal], оказываются более удобными.

Отметим, наконец, что один и тот же язык может быть задан регулярными выражениями, которые выглядят совершенно по-разному. Читатель может при желании проверить, что регулярные выражения

задают один и тот же язык; в свою очередь регулярные выражения

тоже залают один язык.