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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
Строка 24: Строка 23:
 
}}
 
}}
  
== Пример ==
+
=== Пример ===
 
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]
 
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]
  
 
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <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> 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> D_i </tex> существует рекуррентная формула:
 
* <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>.
 
 
Осталось найти такое <tex> k </tex> и <tex> D_k </tex>, что <tex> E_k = \varnothing </tex> тогда мы узнаем пары неэквивалентных состояний, останется только проверить, что <tex> \langle s_1, s_2 \rangle \notin D_k </tex>, тогда автоматы будут эквивалентны.
 
 
Будем строить <tex> D_i </tex> в порядке увеличения <tex> i </tex>, пока <tex> D_i \neq D_{i - 1}</tex>.
 
Заметим, что <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> по рекуррентной формуле, пока не выполнится условие остановки.
 
 
Это можно реализовать проще: будем хранить для каждого состояния, из какого состояния есть переход по символу <tex> c </tex> в наше. В очередь будем класть пары неэквивалентных состояний. Дальше вытаскивая из очереди пару, рассмотрим все пары состояний, из которых есть переход по одинаковому символу в элементы пары из очереди. Пометим их неэквивалентными и положим в очередь.
 
===Псевдокод===
 
<font size = 3>
 
    <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>.
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 19:55, 23 января 2012

Определение:
Два автомата [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] называются эквивалентными, если они распознают один и тот же язык над алфавитом [math]\Sigma[/math], то есть [math]\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)[/math].


Определение:
Слово [math]z \in \Sigma^*[/math] различает два состояния [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] \forall z \in \Sigma^*\ \forall q \in Q \ \exists ! t : \langle q, z \rangle \vdash^* \langle t, \varepsilon \rangle [/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]. Стартовые и все допускающие состояния автоматов эквивалентны между собой.