Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Альтернативное доказательство: Заменил сумму на объединение (чтобы не путать сигму с алфавитом); грамматика)
Строка 46: Строка 46:
 
* [[Теорема Клини (совпадение классов автоматных и регулярных языков) | Теорема Клини]]
 
* [[Теорема Клини (совпадение классов автоматных и регулярных языков) | Теорема Клини]]
 
* [[Решение уравнений в регулярных выражениях | Решение уравнений в регулярных выражениях ]]
 
* [[Решение уравнений в регулярных выражениях | Решение уравнений в регулярных выражениях ]]
 +
 +
== Источники информации==
 +
* [https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/regular-exp.pdf Regular Expressions {{---}} Deepak D’Souza]
 +
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 19:55, 3 января 2017

Альтернативное доказательство

Теорема:
Класс автоматных языков является подмножеством регулярных.
Доказательство:
[math]\triangleright[/math]
Автомат1.png

Рассмотрим автоматный язык [math]L[/math] и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык [math]L[/math].

Пусть наш автомат состоит из [math]n[/math] состояний, и состояние [math]0[/math] — стартовое. Также пусть [math]L_i[/math] — язык, состоящий из слов, которые приводят из состояния [math]i[/math] в терминальное.

Заметим, что [math]L_i = \bigcup c L_j[/math] для всех [math] c \in \Sigma [/math] и [math]j[/math] таких, что [math]\delta(i, c)=j[/math]. Действительно, если по слову [math] \alpha [/math] из состояния [math]j[/math] мы можем попасть в терминальное состояние, а между состояниями [math] i [/math] и [math] j [/math] есть переход по символу [math] c [/math], то слово [math] c \alpha [/math] принадлежит языку [math]L_i[/math]. Также, если [math]\varepsilon \in L_i[/math], то есть если состояние является терминальным, то добавим [math]\varepsilon[/math] в объединение для [math]L_i[/math].

Мы получили систему из [math]n[/math] регулярных выражений с [math]n[/math] неизвестными, причем [math] \varepsilon \notin \alpha_{ij}[/math] ([math] \alpha_{ij} [/math] — коэффициент перед [math] j [/math]-й переменной в [math] i [/math] уравнении) для всех [math] i [/math] и [math] j [/math], так как в автомате нет [math] \varepsilon [/math]-переходов, а следовательно, система имеет единственное решение. Также заметим, что [math]L_0[/math] содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда [math]L_0 = L[/math].

В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим регулярное выражение, порождающее язык [math]L[/math].
[math]\triangleleft[/math]

Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по теореме Клини.

Пример

Автомат2.png

Найдем регулярное выражение для языка двоичных представлений чисел кратных трем.

[math] \begin{cases} L_0 = 0L_0+1L_1+\varepsilon \\ L_1 = 1L_0+0L_2 \\ L_2 = 0L_1+1L_2 \end{cases} [/math]

Выразим [math]L_2[/math] из третьего уравнения, подставив [math] L_1 [/math] из второго:

[math]L_2 = (00 + 1)L_2+01L_0[/math].

Так как [math] \varepsilon \notin (00 + 1) [/math], то [math]L_2 = (00+1)^*01L_0[/math].

Подставим [math]L_2[/math] во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти [math]L_0[/math]:

[math]L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \varepsilon [/math].

Решив уравнение, получим что [math](0 + 11 + 10(00+1)^*01)^*[/math] — регулярное выражение, порождающее искомый язык.

См. также

Источники информации