403
правки
Изменения
→Альтернативное доказательство
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> {{---}} стартовое. Также пусть <tex>L_i</tex> {{---}} язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
Заметим, что <tex>L_i = \sum 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>с \alpha</tex> принаджелит языку <tex>L_i</tex>. Также, если <tex>\epsilon \in \L_0</tex>, то есть если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0</tex> и <tex>\epsilon</tex>.
Заметим, что <tex>L_0 = L</tex>.
}}
== Пример ==
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
