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