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

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

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Рассмотрим автоматный язык [math]L[/math] и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык [math]L[/math]. Пусть наш автомат состоит из [math]n[/math] состояний, и состояние [math]0[/math] — стартовое. Также пусть [math]L_i[/math] — язык, состоящий из слов, которые приводят из состояния [math]i[/math] в терминальное. Заметим, что [math]L_i = \sum 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]

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

Пример

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

[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] — регулярное выражение, порождающее искомый язык.

См. также

• Теорема Клини
• Решение уравнений в регулярных выражениях