Изменения

Перейти к: навигация, поиск

Эквивалентность состояний ДКА

114 байт убрано, 22:50, 8 июня 2016
Псевдокод
'''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''' '''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)$
$\mathtt{used1[aut1}[u][c]] \leftarrow $ ''true'' $\mathtt{used2[aut2}[v][c]] \leftarrow $ ''true''
'''return''' ''true''
Анонимный участник

Навигация