38
правок
Изменения
Нет описания правки
{{Определение
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются <em>эквивалентными</em> <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z\in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow t_1 \in T \Leftrightarrow t_2 \in T </tex>.
}}
Заметим, что эквивалентность состояний действительно является отношением эквивалентности. Так как <tex> \Leftrightarrow </tex> является отношением эквивалентности, и <tex> \forall z \in \Sigma^*\ \forall q \in Q \ \exists ! t : \langle q, z \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, что и доказывает, что описанное нами отношение является отношением эквивалентности.
== Пример ==
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]
