Изменения

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Все Стартовые и все допускающие состояния автоматов эквивалентны между собой.

Алгоритм Оценим время работы алгоритма. Заметим, что каждая пара состояния будет добавлена в очередь, не более одного раза. Поэтому цикл ''while'' выполнится не более чем <tex> |Q_1|\cdot |Q_2| </tex> раз. А значит в этом же цикле каждая пара ребер будет просмотрена не более одного раза, потому что для каждой вершины мы просматриваем все входящие ребра. А значит внутренний <font size = 3><tt> if neq[<tex>e_1</tex>, <tex>e_2</tex>] </tt> </font> выполнится порядка <tex> |Q_1||Q_2||\Sigma|^2 </tex>, потому что это верхняя оценка на количество ребер в детерминированном автомате {{---}} <tex> |Q||\Sigma|</tex>.А значит алгоритм будет работать за <tex> O(|Q_1||Q_2||\Sigma|^2)</tex>.