Эквивалентность состояний ДКА — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
(Проверка через BFS)
Строка 48: Строка 48:
 
Поскольку '''эквивалентные''' автоматы '''допускают''' один  тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно '''терминальными''', либо одновременно '''нетерминальными''', что и проверяет приведённый алгоритм.  
 
Поскольку '''эквивалентные''' автоматы '''допускают''' один  тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно '''терминальными''', либо одновременно '''нетерминальными''', что и проверяет приведённый алгоритм.  
  
 +
<wikitex>
 
Псевдокод:
 
Псевдокод:
  bfs_equivalence_check(aut1, aut2)
+
  <font color=green>// <tex>Q</tex> {{---}} очередь из пар состояний</font>
     '''insert''' <tex>\{s_1, s_2\}</tex> in <tex>Q </tex>
+
'''function''' $\mathtt{bfsEquivalenceCheck}$($aut1$, $aut2$)
     used1[0] <tex> \leftarrow </tex> true;
+
     $\mathtt{insert} \langle s_1, s_2 \rangle in Q $
     used2[0] <tex> \leftarrow </tex> true;
+
     $\mathtt{used1[0]\leftarrow $ ''true''
     '''while''' <tex>Q \ne \varnothing </tex>  
+
     $\mathtt{used2[0]\leftarrow $ ''true''
         u <tex> \leftarrow </tex> Q.front.first;
+
     '''while''' $Q \ne \varnothing $  
         v <tex> \leftarrow </tex> Q.front.second;
+
         $u \leftarrow Q.front.first$
         pop(Q);
+
         $v \leftarrow Q.front.second$
         '''if'''(isTerminal1[u] != isTerminal2[v])
+
         $\mathtt{pop(Q)}$
             '''return''' false;
+
         '''if'''( $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$ )
         '''for''' <tex>i \in \Sigma</tex>
+
             '''return''' ''false''
             '''if'''(!used1[aut1[u][i]] || !used2[aut2[v][i]])
+
         '''for''' $i \in \Sigma$
                 '''insert''' <tex>\{</tex>aut1[u][i], aut2[v][i]<tex>\}</tex> in <tex>Q</tex>
+
             '''if'''( '''not''' $\mathtt{used1[aut1[u][i]]}$ || '''not''' $\mathtt{used2[aut2[v][i]]} $)
                 used1[aut1[u][i]] <tex> \leftarrow </tex> true;
+
                 '''insert''' $ \langle \mathtt{aut1[u][i]}, \mathtt{aut2[v][i]} \rangle \in Q $
                 used2[aut2[v][i]] <tex> \leftarrow </tex> true;
+
                 $\mathtt{used1[aut1[u][i]]} \leftarrow $ ''true''
 +
                 $\mathtt{used2[aut2[v][i]]} \leftarrow $ ''true''
 
     '''return''' true;
 
     '''return''' true;
 +
</wikitex>
  
 
Замечание: в данной реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].
 
Замечание: в данной реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].

Версия 14:42, 18 октября 2014

Основные определения

Определение:
Два автомата [math] \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle [/math] и [math]\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle [/math] называются эквивалентными (англ. equivalent), если они распознают один и тот же язык над алфавитом [math]\Sigma[/math], то есть [math]\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)[/math].


Определение:
Слово [math]z \in \Sigma^*[/math] различает (англ. distinguish) два состояния [math]q_i[/math] и [math]q_j[/math], если
  • [math] \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) [/math].


Определение:
Два состояния [math]q_i[/math] и [math]q_j[/math] называются эквивалентными [math](q_i \sim q_j)[/math], если не существует строки, которая их различает, то есть [math]\forall z \in \Sigma^*[/math] верно, что
  • [math] \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) [/math].


Заметим, что эквивалентность состояний действительно является отношением эквивалентности. Так как [math] \Leftrightarrow [/math] (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

Лемма:
[math] \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle [/math], [math] p_1, p_2, q_1, q_2 \in Q [/math], [math] q_i = \delta(p_i, c) [/math], [math] w \in \Sigma^*[/math] различает [math] q_1 [/math] и [math] q_2 [/math]. Тогда [math]cw[/math] различает [math] p_1 [/math] и [math] p_2 [/math].
Доказательство:
[math]\triangleright[/math]

[math] \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle [/math]

А значит, по условию различимости для [math] q_1 [/math] и [math] q_2[/math] , [math] t_1 \in T \Leftrightarrow t_2 \notin T [/math]
[math]\triangleleft[/math]

Пример

Avtomat2.png Avtomat3.png

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

Проверка ДКА на эквивалентность

Заданы два автомата: [math] \mathcal{A}_1 [/math] со стартовым состоянием [math] s_1 [/math] и [math] \mathcal{A}_2 [/math] со стартовым состоянием [math] s_2 [/math] соответственно. Нужно проверить их на эквивалентность.

Проверка через минимизацию

Для этого построим автомат [math] \mathcal{A} [/math], содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать [math] s_1 [/math] или [math] s_2 [/math] — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новый стартовой вершины в новом автомате, но для алгоритма это и не важно.
Auto equiq.png
Осталось лишь проверить на эквивалентность состояния [math] s_1 [/math] и [math] s_2 [/math] в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов [math] \mathcal{A}_1 [/math] и [math] \mathcal{A}_2 [/math]. Для этого можно применить алгоритм минимизации ДКА, который разбивает все состояния на классы эквивалентности. Если состояния [math]s_1[/math] и [math]s_2[/math] нового автомата в одном классе эквивалентности — исходные автоматы эквивалентны.

Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.

Замечание: для реализации оба автомата обязательно должны иметь дьявольские состояния.

Проверка через BFS

Алгоритм заключается в синхронном обходе автоматов в ширину, проверяя, что по пути сохраняются терминальные состояния. Поскольку эквивалентные автоматы допускают один тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм.

<wikitex> Псевдокод:

// [math]Q[/math] — очередь из пар состояний
function $\mathtt{bfsEquivalenceCheck}$($aut1$, $aut2$)
    $\mathtt{insert} \langle s_1, s_2 \rangle in Q $
    $\mathtt{used1[0]}  \leftarrow $ true
    $\mathtt{used2[0]}  \leftarrow $ true
    while $Q \ne \varnothing $  
        $u \leftarrow Q.front.first$
        $v \leftarrow Q.front.second$
        $\mathtt{pop(Q)}$
        if( $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$ )
            return false
        for $i \in \Sigma$
            if( not $\mathtt{used1[aut1[u][i]]}$ ||  not $\mathtt{used2[aut2[v][i]]} $)
                insert $ \langle \mathtt{aut1[u][i]}, \mathtt{aut2[v][i]} \rangle \in Q $
                $\mathtt{used1[aut1[u][i]]} \leftarrow $ true
                $\mathtt{used2[aut2[v][i]]} \leftarrow $ true
    return true;

</wikitex>

Замечание: в данной реализации оба автомата обязательно должны иметь дьявольские состояния.

См. также

Источники информации