171
правка
Изменения
Нет описания правки
return dfs(a.start);
}
== Совпадение ==
'''Совпадение''' двух [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] — свойство, при выполнении которого любое слово, принадлежащее одному из языков, принадлежит второму.
Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''идентичными''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>,
где <tex>s_{1}</tex>, <tex>s_{2}</tex> - стартовые состояния.
На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу тогда и только тогда, когда существует последовательность состояний <tex>p_{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>. Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут.
{{Утверждение
|id=
regEqClasses
|statement=
Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда в любом классе содержатся или только допускающие, или только недопускающие состояния.
|proof=
Пусть в каком-либо классе содержатся допускающее состояние <tex>t</tex> и недопускающее <tex>u</tex>. По построению классов эквивалентности, существует последовательность <tex>p_{0}...p_{k}</tex>, где <tex>t = p_{0}</tex>, <tex>u = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>. Тогда найдётся пара <tex>p_{j}</tex>, <tex>p_{j+1}</tex>: <tex>p_{j}</tex> является допускающим, а <tex>p_{j+1}</tex> - нет. Для определённости, пусть <tex>p_{j}</tex> принадлежит первому автомату, а <tex>p_{j+1}</tex> - второму. Так как эти состояния идентичны, <tex>\exists w</tex>:
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{j}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{j+1}, \epsilon \rangle</tex>.
Таким образом, слово <tex>w</tex> допускается первым автоматом и не допускается вторым, значит, автоматы неэквивалентны.
Пусть в любом классе содержатся только допускающие или только недопускающие состояния. Рассмотрим любую строку <tex>w</tex> и такие состояния <tex>u_{1}</tex> и <tex>u_{2}</tex>, что
<tex>\langle s_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>.
Состояния <tex>u_{1}</tex> и <tex>u_{2}</tex> идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями в обоих автоматах, либо в обоих не допускается, значит, автоматы эквивалентны.
}}
{{Утверждение
|id=
regEqClasses
|statement=
Если состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу эквивалентности, то для любого символа <tex>c</tex> из алфавита <tex>\delta (p, c)</tex> и <tex>\delta (q, c)</tex> также принадлежат одному классу.
|proof=
Рассмотрим последовательность <tex>p_{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex> по строке <tex>w_{i}</tex>. Тогда для последовательности <tex>p'_{0}...p'_{k}</tex>, где <tex>\delta (p, c) = p'_{0}</tex>, <tex>\delta (q, c) = p_{k}</tex> будет верно: <tex>\forall i = 1..k</tex> <tex>p'_{i - 1}</tex> идентично <tex>p'_{i}</tex> по строке <tex>w_{i}c</tex>. Таким образом, <tex>\delta (p, c)</tex> и <tex>\delta (q, c)</tex> также принадлежат одному классу.
}}
По индукции, утверждение верно и для большего числа переходов.
=== Алгоритм проверки языков на эквивалентность ===
Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов.
Второй шаг - обход в ширину, объединяющий классы эквивалентности. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется [[СНМ(наивные реализации)|система непересекающихся множеств]]. Очередь обхода в ширину хранит пары состояний <tex>p_{1} \in A_{1}</tex>, <tex>p_{2} \in A_{2}</tex>, для которых существует строка <tex>w</tex> (для <tex>s_{1}</tex> и <tex>s_{2}</tex> равная <tex>\epsilon</tex>):
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>.
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть <tex>\delta (p_{1}, c) = q_{1}</tex>, <tex>\delta (p_{2}, c) = q_{2}</tex>.
