142
правки
Изменения
Нет описания правки
==Основные определения==
{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</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 \notin T \Leftrightarrow t_2 \in T ) </tex>.
}}
{{Определение
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <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>, поэтому описанное нами отношение является отношением эквивалентности.
{{Лемма
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}
== Пример ==
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.
== Алгоритм проверки эквивалентности автоматов ==
