Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
Альтернативное доказательство
| Теорема: |
Класс автоматных языков является подмножеством регулярных. |
| Доказательство: |
 Рассмотрим автоматный язык и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык . Пусть наш автомат состоит из состояний, и состояние — стартовое. Также пусть — язык, состоящий из слов, которые приводят из состояния в терминальное. Заметим, что для всех и таких, что . Действительно, если по слову из состояния мы можем попасть в терминальное состояние, а между состояниями и есть переход по символу , то слово принаджелит языку . Также, если , то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для и . Мы получили систему из регулярных выражений с неизвестными, причем для всех и , так как в автомате нет -переходов, следовательно, система имеет единственное решение. Также заметим, что содержит слова, по которым из стартового состояния можно дойти до терминального, но тогда . В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык . |
Пример
Найдем регулярное выражение для языка двоичных представлений чисел кратных трем.
Выразим :
.
Так как , то .
Подставим во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти :
.
Решив уравнение, получим что — регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.
