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