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

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

Теорема:

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

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

[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]\epsilon \in L_0[/math], то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для [math]L_0[/math] и [math]\epsilon[/math]. Мы получили систему из [math]n[/math] регулярных выражений с [math]n[/math] неизвестными, причем для всех [math] i [/math] и [math] j [/math] [math] \epsilon \notin \alpha_{ij}[/math], так как в автомате нет [math] \epsilon [/math]-переходов, следовательно, система имеет единственное решение. Также заметим, что [math]L_0[/math] содержит слова, по которым из стартового состояния можно дойти до терминального, но тогда [math]L_0 = L[/math]. В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим реглярное выражение порождающее язык [math]L[/math].

[math]\triangleleft[/math]