Изменения

Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> {{---}} — стартовое. Также пусть <tex>L_i</tex> {{---}} — язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.

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

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