Эквивалентность состояний ДКА

Эквивалентность автоматов

Определение:

Два автомата [math] \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{10}, T_1\subseteq Q_1 \rangle [/math] и [math]\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{20}, T_2\subseteq Q_2 \rangle [/math] называются эквивалентными, если они распознают один и тот же язык над алфавитом [math]\Sigma[/math], то есть [math]\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)[/math]

Определение:

Слово [math]z \in \Sigma^*[/math] различает два состояния [math]q_i[/math] и [math]q_j[/math], если [math] \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 [/math].

Определение:

Два состояния [math]q_i[/math] и [math]q_j[/math] называются эквивалентными [math](q_i \sim q_j)[/math], если не существует строки, которая их различает, то есть [math]\forall z\in \Sigma^*[/math] верно, что [math] \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 [/math].

• Пример двух эквивалентных автоматов:

Состояния [math]B[/math] и [math]C[/math] допускающие.