Изменения
→Проверка через BFS
Замечание: в данной реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].
<wikitex>
Доказательство корректности:
Пусть по строке $w$ мы пришли в состояния $ \langle u, v \rangle $, и пусть они нетерминальные.
Пусть мы перешли по символу $c$ в состояние $ \langle u', v' \rangle $ ($u$ может быть равно $u'$ или $v'$ может быть равно $u'$, но не оба сразу).
Тогда если $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.
</wikitex>
== См. также ==
