Изменения
Нет описания правки
== Основные определения ==
{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
Псевдокод:
bfs_equivalence_check(aut1, aut2) queue.push( '''insert''' <tex>\{0, 0\}</tex> in <tex>Q </tex> ); used1[0] = <tex> \leftarrow </tex> true; used2[0] = <tex> \leftarrow </tex> true; '''while( !q.isEmpty() )''' <tex>Q \ne \varnothing </tex> u = q<tex> \leftarrow </tex> Q.front.first; v = q<tex> \leftarrow </tex> Q.front.second; q.pop(Q); '''if'''(isTerminal1[u] != isTerminal2[v]) '''return ''' false; '''for(''' <tex>i = a..z)\in \Sigma</tex> '''if'''(!used1[automata1aut1[u][i]] || !used2[automata2aut2[v][i]]) q.push( '''insert''' <tex>\{<automata1/tex>aut1[u][i], automata2aut2[v][i]<tex>\}</tex> in <tex>Q</tex> ); used1[automata1aut1[u][i]] = <tex> \leftarrow </tex> true; used2[automata2aut2[v][i]] = <tex> \leftarrow </tex> true; '''return ''' true;
Замечание: в данной реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].
