Изменения

Перейти к: навигация, поиск

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

280 байт добавлено, 07:23, 1 октября 2010
Эквивалентность автоматов
*'''Определение:''' Слово <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|}\hlineQ\diagdown \Sigma & a & b\\\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>
</font>
Анонимный участник

Навигация