1632
правки
Изменения
м
<wikitex>
$\mathtt{used1[aut1}[u][c]] \leftarrow $ ''true''
$\mathtt{used2[aut2}[v][c]] \leftarrow $ ''true''
</wikitex>
rollbackEdits.php mass rollback
Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов. То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого.
Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм.
==== Псевдокод ====
<font color=green>// $\mathtt{aut}[i][c]$ {{---}} номер состояния, в которое есть переход из состояния $i$ по символу $c$</font>
'''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> $\mathtt{used1}[s_1] \leftarrow $ ''true'' $\mathtt{used2}[s_2] \leftarrow $ ''true''
'''while''' $Q \ne \varnothing $
$u, v \leftarrow Q.\mathtt{pop}()$
'''if''' $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$
'''return''' ''false''
$\mathtt{used[u][v]} \leftarrow $ ''true''
'''for''' $c \in \Sigma$
'''if''' '''not''' $\mathtt{used1used[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''
Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.
== См. также ==
