Изменения
→Эквивалентность автоматов
*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(s_i \nsim s_j)</tex>, если <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_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>.
*'''Пример двух эквивалентных автоматов:''' <math>\begin{array}{|c|c|c|} \hline Q\diagdown \Sigma & a & b\\\hline\hline A & B & C\\\hline B & B & D\\\hline C & B & C\\\hline D & B & E\\\hline E & B & C\\\hline F & E & E\\
\hline
\end{array}
</math> <tex>\sim</tex> <math>
\begin{array}{|c|c|c|}
\hline
Q\diagdown \Sigma & a & b\\
\hline A \hline - & B & C\\
\hline B & B & D\\
\hline C & B & C\\
\hline D & B & E\\
\hline E & B & C\\
\hline F - & E & E\\
\hline
\end{array}
