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

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

Теорема:

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

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

[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] с \alpha [/math] принаджелит языку [math]L_i[/math]. Также, если [math]\epsilon \in L_0[/math], то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для [math]L_0[/math] и [math]\epsilon[/math]. Заметим, что [math]L_0 = L[/math].

[math]\triangleleft[/math]