Изменения
→Псевдокод
Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов. То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого.
Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм.
==== Псевдокод ====
<wikitex>
'''boolean''' $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : '''int[][]''', $\mathtt{aut2}$ : '''int[][]'''):
$Q.\mathtt{push}(\langle s_1, s_2 \rangle) $ <font color=green>// <tex>Q</tex> {{---}} очередь из пар состояний</font>
'''while''' $Q \ne \varnothing $
$u, v \leftarrow Q.\mathtt{pop}()$
'''if''' $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$
'''return''' ''false''
$\mathtt{used1[u]} \leftarrow $ ''true''
$\mathtt{used2[v]} \leftarrow $ ''true''
'''for''' $c \in \Sigma$
'''if''' '''not''' $\mathtt{used1[aut1}[u][c]]$ '''or''' '''not''' $\mathtt{used2[aut2}[v][c]]$
$Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$
'''return''' ''true''
