Изменения

*'''Определение: ''' Два <em> состояния</em> <tex>s_iq_i</tex> и <tex>s_jq_j</tex> называются <em>эквивалентными</em> <tex>(s_i q_i \sim s_jq_j)</tex>, если <tex>\forall z\in \Sigma^*</tex> верно, что <tex>\delta(s_iq_i, z)\in T \Leftrightarrow \delta(s_jq_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>s_iq_i</tex> и <tex>s_jq_j</tex> эквивалентны, то и состояния <tex>\delta_1(s_iq_i, a)</tex> и <tex>\delta_2(s_jq_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(sq, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>sq</tex>, то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за <tex>O(n \log n)</tex>.*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(s_i q_i \nsim s_jq_j)</tex>, если <tex>\delta(s_iq_i, z)\in T \Leftrightarrow \delta(s_jq_j, z)\notin T</tex>. Также, если слово <tex>z</tex> различает состояния <tex>t_1</tex> и <tex>t_2</tex> такие, что <tex>t_1=\delta(q_1, a)</tex> и <tex>t_2=\delta(q_2, a)</tex>, то слово <tex>aw</tex> различает состояния <tex>q_1</tex> и <tex>q_2</tex>. Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за <tex>O(n^2)</tex>.

[[Изображение:Automata1.png]][[Изображение:Automata2.png]] <em>Состояния <tex>B</tex> и <tex>C</tex> допускающие.</em> </font>== Проверка эквивалентности автоматов == <font face="Times" size="3">*Если положить, что начальные состояния эквивалентны, то последовательно, переходя по одному символу из состояний, можем получить и другие пары эквивалентных состояний. Если же в одну из таких пар попадут допускающее состояния вместе с не допускающим, то такие <tex>q_i</tex> и <tex>q_j</tex> неэквивалентны.<tex>AlgoPartition(Q_1, Q_2, q_{10}, q_{20}){}</tex>