|
|
| Строка 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>.
| |
| | | | |
| | [[Категория: Теория формальных языков]] | | [[Категория: Теория формальных языков]] |
| | [[Категория: Автоматы и регулярные языки]] | | [[Категория: Автоматы и регулярные языки]] |
