Изменения
→Проверка через BFS
=== Проверка через BFS ===
Алгоритм заключается в синхронном обходе автоматов в ширину, проверяя, что по пути сохраняются терминальные состояния.
Поскольку '''эквивалентные''' автоматы '''допускают''' один тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно '''терминальными''', либо одновременно '''нетерминальными''', что и проверяет приведённый алгоритм.
Псевдокод:
Замечание: в данной реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].
== См. также ==
