Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) — различия между версиями
Warrior (обсуждение | вклад) м (→Альтернативное доказательство) |
Warrior (обсуждение | вклад) м (→Альтернативное доказательство) |
||
| Строка 17: | Строка 17: | ||
}} | }} | ||
| − | Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по теореме Клини. | + | Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]]. |
== Пример == | == Пример == | ||
Версия 17:55, 26 октября 2013
Альтернативное доказательство
| Теорема: |
Класс автоматных языков является подмножеством регулярных. |
| Доказательство: |
 Рассмотрим автоматный язык и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык . Пусть наш автомат состоит из состояний, и состояние — стартовое. Также пусть — язык, состоящий из слов, которые приводят из состояния в терминальное. Заметим, что для всех и таких, что . Действительно, если по слову из состояния мы можем попасть в терминальное состояние, а между состояниями и есть переход по символу , то слово принаджелит языку . Также, если , то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для и . Мы получили систему из регулярных выражений с неизвестными, причем ( — коэффициент перед -й переменной в -м уравнении) для всех и , так как в автомате нет -переходов, а, следовательно, система имеет единственное решение. Также заметим, что содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда . В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык . |
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по теореме Клини.
Пример
Найдем регулярное выражение для языка двоичных представлений чисел кратных трем.
Выразим :
.
Так как , то .
Подставим во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти :
.
Решив уравнение, получим что — регулярное выражение, порождающее искомый язык.
