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