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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 59 промежуточных версий 13 участников)
Строка 1: Строка 1:
==Основные определения==
+
== Связь эквивалентности состояний и различимости состояний ==
 +
 
 
{{Определение
 
{{Определение
|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>.
+
|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> называются '''эквивалентными''' (англ. ''equivalent''), если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если  
+
|definition = [[Основные определения, связанные со строками#string|Слово]] <tex>z \in \Sigma^*</tex> '''различает''' (англ. ''distinguish'')  два состояния <tex>q_i</tex> и <tex>q_j</tex>, если  
 
* <tex> \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) </tex>.
 
* <tex> \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) </tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex>  верно, что
+
|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует [[Основные определения, связанные со строками#string|строки]], которая их различает, то есть <tex>\forall z \in \Sigma^*</tex>  верно, что
 
* <tex> \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) </tex>.
 
* <tex> \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) </tex>.
 
}}
 
}}
  
Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и <tex> \forall z \in \Sigma^*\  \forall q \in Q \  \exists ! t : \langle q, z \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, описанное нами отношение является отношением эквивалентности.
+
Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.
  
 
{{Лемма
 
{{Лемма
Строка 24: Строка 25:
 
}}
 
}}
  
== Пример ==
+
=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]
+
[[Файл:avtomat2.png|200px]] [[Файл:avtomat3.png|200px]]
  
 
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.
 
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.
  
== Алгоритм проверки эквивалентности автоматов ==
+
[[Категория: Теория формальных языков]]
===Постановка задачи===
+
[[Категория: Автоматы и регулярные языки]]
Даны два детерминированных конечных автомата <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> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
* <tex> D_i = \lbrace \langle q, p\rangle | q \in Q_1, p \in Q_2, \exists w : |w| \le i, w </tex> различает <tex> q </tex> и <tex> p \rbrace </tex>;
+
 
* <tex> E_i = D_i \setminus D_{i - 1} </tex>.
+
'''Замечание:''' для реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].
 +
=== Проверка через минимизацию ===
 +
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> s_2 </tex> — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новой стартовой вершины в новом автомате, но для алгоритма это и не важно.<br>
 +
[[Файл:auto_equiq.png|470px]]<br>
 +
Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> и <tex> s_2 </tex> в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex>s_1</tex> и <tex>s_2</tex> нового автомата в одном классе эквивалентности {{---}} исходные автоматы эквивалентны.
 +
 
 +
Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.
  
Для <tex> D_i </tex> существует рекуррентная формула:
+
=== Проверка через BFS ===
* <tex> D_i = D_{i - 1} \cup \lbrace \langle p, q \rangle | \exists c \in \Sigma : \langle \delta(p, c), \delta(q, c) \rangle \in E_{i - 1} \rbrace </tex>.
+
Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов. То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого.
То есть <tex> D_i </tex> {{---}} объединение множества всех пар состояний, которые различаются строками длины меньшей <tex> i </tex> с множеством всех пар состояний, которые различаются строками длины ровно <tex>i</tex>.
 
  
Заметим, что <tex> \exists k : E_k = \varnothing </tex>, причем <tex> k \le |Q| ^ 2</tex>. Также заметим, что <tex> E_k = \varnothing \Rightarrow E_{k + 1} = \varnothing </tex>, так как в <tex> D_{k+1}</tex> новых элементов не добавится, поэтому <tex> D_{k+1} = D_k </tex>.
+
Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм.
Значит:
+
==== Псевдокод ====
* <tex> E_k = \varnothing \Rightarrow D_k = \lbrace \langle q, p\rangle | q \in Q_1, p \in Q_2, \exists w : w </tex> различает <tex> q </tex> и <tex> p \rbrace = \lbrace \langle q, p\rangle | (q \nsim p)\rbrace</tex>.
+
<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>
 +
    '''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{used[aut1[u][c]][aut2[v][c]]}$
 +
                $Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$
 +
    '''return''' ''true''
  
Осталось найти такое <tex> k </tex> и <tex> D_k </tex>, что <tex> E_k = \varnothing </tex> тогда мы узнаем пары неэквивалентных состояний, останется только проверить, что <tex> \langle s_1, s_2 \rangle \notin D_k </tex>, тогда автоматы будут эквивалентны.
+
Корректность алгоритма следует из строго доказательства того факта, что если два состояния $u$ и $v$ различаются какой-то строкой, то они различаются строкой длины $O(n)$.
  
Будем строить <tex> D_i </tex> в порядке увеличения <tex> i </tex>, пока <tex> D_i \neq D_{i - 1}</tex>.
+
Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в состояния  $ \langle u, v \rangle $, и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \langle u', v' \rangle $.  
Заметим, что <tex> D_0 = \lbrace \langle p, q\rangle | p \in T_1 \Leftrightarrow q \notin T_2 \rbrace </tex>, так как строка длины 0 одна {{---}} это <tex> \varepsilon </tex>, а <tex> \varepsilon </tex> различает только пары состоящие из одного терминального состояния и одного нетерминального.
 
  
Дальше будем получать <tex> D_i </tex> по рекуррентной формуле, пока не выполнится условие остановки.
+
Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.
  
Это можно реализовать проще: будем хранить для каждого состояния, из какого состояния есть переход по символу <tex> c </tex> в наше. В очередь будем класть пары неэквивалентных состояний. Дальше вытаскивая из очереди пару, рассмотрим все пары состояний, из которых есть переход по одинаковому символу в элементы пары из очереди. Пометим их неэквивалентными и положим в очередь.
+
== См. также ==  
===Псевдокод===
+
* [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|Алгоритм минимизации ДКА]]
<font size = 3>
+
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
    <tex> q = \varnothing </tex>
 
    fill(neq, false)
 
    for <tex> p_1 \in Q_1 </tex>
 
        for <tex> p_2 \in Q_2 </tex>
 
            if <tex> (p_1 \in T_1) \neq (p_2 \in T_2) </tex>
 
                q.push(<tex>p_1</tex>,<tex> p_2</tex>)
 
                neq[<tex>p_1</tex>, <tex>p_2</tex>] = True
 
    while not isEmpty(q)
 
        <tex> \langle p_1, p_2 \rangle </tex> = q.pop()
 
        for <tex> c \in \Sigma </tex>
 
            for <tex> \delta(e_1, c) = p_1 </tex>
 
                for <tex> \delta(e_2, c) = p_2 </tex>
 
                    if neq[<tex>e_1</tex>, <tex>e_2</tex>]
 
                        continue
 
                    q.push(<tex>e_1</tex>, <tex>e_2</tex>)
 
                    neq[<tex>e_1</tex>, <tex>e_2</tex>] = True
 
    if neq[<tex>s_1</tex>, <tex>s_2</tex>]
 
        print("Not equivalent")
 
    else
 
        print("Equivalent")
 
</font>
 
===Время работы алгоритма===
 
Оценим время работы алгоритма. Заметим, что каждая пара состояния будет добавлена в очередь, не более одного раза. Поэтому цикл ''while'' выполнится не более чем <tex> |Q_1|\cdot |Q_2| </tex> раз. А значит в этом же цикле каждая пара ребер будет просмотрена не более одного раза, потому что для каждой вершины мы просматриваем все входящие ребра. А значит внутренний <font size = 3><tt> if neq[<tex>e_1</tex>, <tex>e_2</tex>] </tt> </font> выполнится порядка <tex> |Q_1||Q_2||\Sigma|^2 </tex>, потому что это верхняя оценка на количество ребер в детерминированном автомате {{---}} <tex> |Q||\Sigma|</tex>.
 
А значит алгоритм будет работать за <tex> O(|Q_1||Q_2||\Sigma|^2)</tex>.
 
  
[[Категория: Теория формальных языков]]
+
== Источники информации ==
[[Категория: Автоматы и регулярные языки]]
+
* [http://stackoverflow.com/questions/6905043/equivalence-between-two-automata/12623361#12623361 StackOverflow {{---}} Equivalence between two automata]

Текущая версия на 19:33, 4 сентября 2022

Связь эквивалентности состояний и различимости состояний

Определение:
Два автомата [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

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

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

Псевдокод

// $\mathtt{aut}[i][c]$ — номер состояния, в которое есть переход из состояния $i$ по символу $c$
boolean $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : int[][], $\mathtt{aut2}$ : int[][]):
    $Q.\mathtt{push}(\langle s_1, s_2 \rangle) $ // [math] Q [/math] — очередь из пар состояний
    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{used[aut1[u][c]][aut2[v][c]]}$
                $Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$
    return true

Корректность алгоритма следует из строго доказательства того факта, что если два состояния $u$ и $v$ различаются какой-то строкой, то они различаются строкой длины $O(n)$.

Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в состояния $ \langle u, v \rangle $, и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \langle u', v' \rangle $.

Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны.

См. также

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