=== Алгоритм ===
Будем проверять множества переходов для двух вершин. Запустим [[Обход в глубину, цвета вершин | обход в глубину]] из стартовых вершинИз определения следует, что если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольскиеавтоматы изоморфны, то множество переходов считаем равными) то два автомата изоморфны. Заметимможно их состояния занумеровать одним способом так, что если мы рассмотрим два автомата состоящих вершины из пройденных вершин, разных автоматов с одинаковыми номерами будут равны — то эти два автомата будут изоморфны (есть в каждом из этого следуетэтих двух состояний существует переход в какое-то состояние с таким же номером, что и переход по этой же букве в другом состоянии. Поэтому мы можем зафиксировать какую-то нумерацию, например, в порядке обхода в глубину по символам в лексикографическом порядке и просто проверить состояния с одинаковыми номерами на когда мы обойдем равенство. Если все вершинысостояния будут равны то автоматы будут равны, это тоже в нашем случае будет выполнено)следовать изоморфизм двух автоматов. Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз2 раза (нумерация вершин + проверка на равенство), из этого следует время работы <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.
=== Псевдокод ===
