171
правка
Изменения
м
Нет описания правки
На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу тогда и только тогда, когда существует последовательность состояний <tex>p_{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>. Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут.
{{УтверждениеТеорема
|id=
regEqClasses
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>.
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть <tex>\delta (p_{1}, c) = q_{1}</tex>, <tex>\delta (p_{2}, c) = q_{2}</tex>. Если <tex>q_{1}</tex> и <tex>q_{2}</tex> принадлежат разным классам, их классы объединяются, а пара <tex>\langle q_{1}, q_{2} \rangle</tex> добавляется в очередь.
