|
|
Строка 54: |
Строка 54: |
| }} | | }} |
| | | |
− | Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> — [[Детерминированные конечные автоматы| детерминированные конечные автоматы]], задающие языки <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков ('''эквивалентность''' задающих их автоматов) означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1}</tex> из <tex>A_{1}</tex> и <tex>p_{2}</tex> из <tex>A_{2}</tex> '''различимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется
| + | Для проверки совпадения языков достаточно запустить алгоритм проверки [[Эквивалентность_состояний_ДКА|эквивалентности]] задающих их автоматов. |
− | | |
− | <tex>\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>
| |
− | | |
− | или
| |
− | | |
− | <tex>\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle</tex>,
| |
− | | |
− | где <tex>t_{1}</tex>, <tex>t_{2}</tex> — допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> — недопускающие.
| |
− | | |
− | Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами; назовём их '''бесполезными'''. Введём '''сток'''<ref>Другое название стока - «дьявольское состояние».</ref> — специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.
| |
− | | |
− | | |
− | === Алгоритм проверки языков на совпадение ===
| |
− | | |
− | Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, вместо них вводится описанный выше сток.
| |
− | | |
− | | |
− | Пусть <tex>eq(v, u)</tex> — функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма — установка <tex>eq(v, u)</tex> в <tex>false</tex> для всех пар <tex>\langle v, u \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>.
| |
− | | |
− | | |
− | Третий шаг алгоритма — [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle v \in A_{1}, u \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle v', u' \rangle : \delta_{1} (v, c) = v', \delta_{2} (u, c) = u'</tex>. Если <tex>eq(v', u')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle v', u' \rangle</tex>.
| |
− | | |
− | | |
− | {{Теорема
| |
− | |id=
| |
− | regEqual
| |
− | |statement=
| |
− | Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)</tex> возвращает <tex>true</tex> и ровно одно из <tex>\langle v, u \rangle</tex> допускающее.
| |
− | | |
− | |proof=
| |
− | Пусть такой пары не существует. Возьмём произвольное слово <tex>w</tex> длины <tex>n</tex> и выпишем последовательность пар состояний <tex>\langle v_{i}, u_{i} \rangle</tex>: <tex>v_{0} = s_{1}, u_{0} = s_{2}</tex> и <tex>\forall i = 1 .. n</tex> справедливо <tex>\delta_{1} (v_{i-1}, w[i-1]) = v_{i}, \delta_{2} (u_{i-1}, w[i-1]) = u_{i}</tex>. Так как пара <tex>\langle v_{0}, u_{0} \rangle</tex> была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, <tex>eq</tex> для них возвращает <tex>true</tex>. По предположению, или оба состояния <tex>\langle v_{n}, u_{n} \rangle</tex> допускающие в своих автоматах, или оба недопускающие. Таким образом, строка <tex>w</tex> или входит в оба языка, или не входит ни в один.
| |
− | | |
− | | |
− | Пусть такая пара <tex>\langle v, u \rangle</tex> существует. Для определённости скажем, что <tex>v \in A_{1}</tex> — допускающее. Рассмотрим строку <tex>w</tex>, состоящую из символов, в результате переходов по которым из <tex>\langle s_{1}, s_{2} \rangle</tex> в процессе обхода в ширину <tex>eq(v, u)</tex> было установлено в <tex>true</tex>. Строка <tex>w</tex> допускается первым автоматом, но не допускается вторым, значит, автоматы не эквивалентны.
| |
− | }}
| |
− | | |
− | ==== Псевдокод ====
| |
− | | |
− | void reverseDfs(State v):
| |
− | v.canReach = true
| |
− | for each State u in v.prev:
| |
− | if !u.canReach:
| |
− | reverseDfs(u)
| |
− | | |
− | void setSink(Automaton a):
| |
− | State sink = new State
| |
− | for each symbol c in a.alphabet:
| |
− | sink.next(c) = sink
| |
− | for each State v in a:
| |
− | if !v.canReach:
| |
− | v = sink
| |
− | | |
− | void bfs(Automaton a, Automaton b, boolean[][] eq)
| |
− | fill(eq, false)
| |
− | eq[a.start][b.start] = true
| |
− | Queue q = new Queue
| |
− | q.add((a.start, b.start))
| |
− | while !q.isEmpty:
| |
− | (v, u) = q.remove()
| |
− | for each symbol c in a.alphabet: // a.alphabet == b.alphabet
| |
− | v' = v.next(c)
| |
− | u' = u.next(c)
| |
− | if !eq[v'][u']:
| |
− | eq[v'][u'] = true
| |
− | q.add((v', u'))
| |
− | | |
− | boolean areEqual(Automaton a, Automaton b)
| |
− | for each State v in a:
| |
− | v.canReach = false
| |
− | for each State v in a:
| |
− | if v.isFinal:
| |
− | reverseDfs(v)
| |
− | setSink(a)
| |
− | for each State v in b:
| |
− | v.canReach = false
| |
− | for each State v in b:
| |
− | if v.isFinal:
| |
− | reverseDfs(v)
| |
− | setSink(b)
| |
− | eq = new boolean[a.statesNumber][b.statesNumber]
| |
− | bfs(a, b, eq)
| |
− | for each State v in a:
| |
− | for each State u in b:
| |
− | if eq[v][u] && v.isFinal != u.isFinal:
| |
− | return false
| |
− | return true
| |
− | | |
| | | |
| == Включение одного регулярного языка в другой == | | == Включение одного регулярного языка в другой == |
Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт эквивалентности автоматных и регулярных языков.
Пустота регулярного языка
Определение: |
Регулярный язык называется пустым, если он не содержит ни одного слова. |
Язык, содержащий хотя бы одно слово, назовём непустым.
Теорема: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Доказательство: |
[math]\triangleright[/math] |
[math]\Rightarrow[/math]
Пусть язык содержит слово [math]w[/math]. Любой детерминированный конечный автомат [math]A[/math], задающий этот язык, должен допускать [math]w[/math]. Тогда при переходе из стартового состояния [math]A[/math] по символам [math]w[/math] получится путь, оканчивающийся в одном из терминальных состояний.
[math]\Leftarrow[/math]
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку. |
[math]\triangleleft[/math] |
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Псевдокод
boolean dfs(State v):
v.seen = true
if v.isFinal:
return false
for each State u in v.next:
if !u.seen && !dfs(u):
return false
return true
boolean isEmpty(Automaton a):
for each State v in a:
v.seen = false
return dfs(a.start)
Совпадение регулярных языков
Определение: |
Два регулярных языка совпадают, если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.
Включение одного регулярного языка в другой
Определение: |
Регулярный язык [math]L_{1}[/math] входит (включается) в регулярный язык [math]L_{2}[/math], если любое слово, принадлежащее [math]L_{1}[/math], принадлежит [math]L_{2}[/math]. |
Алгоритм проверки на включение
Алгоритм проверки [math]L_{1}[/math] на включение в [math]L_{2}[/math] идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из [math]L_{2}[/math], не входящие в [math]L_{1}[/math], поэтому существование пар [math]\langle v \in L_{1}, u \in L_{2} \rangle : eq(v, u) = true, v \notin T_{1}, u \in T_{2}[/math], где [math]T_{i}[/math] — множества допускающих состояний, не нарушает факт вхождения [math]L_{1}[/math] в [math]L_{2}[/math]. Таким образом, [math]L_{1}[/math] не входит в [math]L_{2}[/math] тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары [math]\langle v, u \rangle[/math], что [math]eq(v, u)[/math] возвращает [math]true[/math], [math]v \in T_{1}, u \notin T_{2}[/math].
Псевдокод
void reverseDfs(State v):
v.canReach = true
for each State u in v.prev:
if !u.canReach:
reverseDfs(u)
void setSink(Automaton a):
State sink = new State
for each symbol c in a.alphabet:
sink.next(c) = sink
for each State v in a:
if !v.canReach:
v = sink
void bfs(Automaton a, Automaton b, boolean[][] eq)
fill(eq, false)
eq[a.start][b.start] = true
Queue q = new Queue
q.add((a.start, b.start))
while !q.isEmpty:
(v, u) = q.remove()
for each symbol c in a.alphabet: // a.alphabet == b.alphabet
v' = v.next(c)
u' = u.next(c)
if !eq[v'][u']:
eq[v'][u'] = true
q.add((v', u'))
boolean belongs(Automaton a, Automaton b)
for each State v in a:
v.canReach = false
for each State v in a:
if v.isFinal:
reverseDfs(v)
setSink(a)
for each State v in b:
v.canReach = false
for each State v in b:
if v.isFinal:
reverseDfs(v)
setSink(b)
eq = new boolean[a.statesNumber][b.statesNumber]
bfs(a, b, eq)
for each State v in a:
for each State u in b:
if eq[v][u] && v.isFinal && !u.isFinal:
return false
return true
Конечность регулярного языка, подсчёт числа слов
Определение: |
Регулярный язык называется конечным, если принадлежащее ему множество слов конечно. |
Теорема: |
Детерминированный конечный автомат [math]A_{1}[/math] задаёт конечный язык тогда и только тогда, когда в [math]A_{1}[/math] не существует состояния [math]v[/math], для которого выполняются три условия:
- [math]v[/math] достижимо из стартового состояния [math]s[/math];
- из [math]v[/math] достижимо какое-либо из допускающих состояний;
- из [math]v[/math] по одному или более переходам достижимо [math]v[/math].
|
Доказательство: |
[math]\triangleright[/math] |
Пусть такое состояние [math]v[/math] существует, а строки [math]x, y, z[/math] таковы, что [math]\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle[/math], [math]t[/math] — допускающее, [math]y[/math] — непустая. Рассмотрим строки вида [math]xy^{k}z, k \in \mathbb{N}[/math]. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено [math]n! | \Sigma |^{n-1}[/math], где [math]n[/math] — количество состояний автомата: [math]n![/math] — количество перестановок состояний, [math]| \Sigma |^{n-1}[/math] — количество совокупностей переходов по символам между ними. Таким образом, язык конечен. |
[math]\triangleleft[/math] |
Алгоритм нахождения числа слов в языке
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию [math]paths(v)[/math], задающую число различных путей из [math]s[/math] в [math]v[/math]; [math]paths(s) = 1[/math]. Заметим, что если известны значения [math]paths(u)[/math] для всех [math]u[/math], из которых существует переход в [math]v[/math], то [math]paths(v) = \sum\limits_{u}paths(u)[/math]. Количеством слов в языке будет сумма [math]paths(t)[/math] для всех допускающих [math]t[/math].
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.
Псевдокод
Stack topSort(Automaton a):
for each State v in a:
v.seen = false
Stack sorted = new Stack
dfsSort(a.start, sorted)
return sorted
void dfsSort(State v, Stack sorted):
v.seen = true
for each State u in v.next:
if !u.seen:
dfsSort(u, sorted)
sorted.push(v)
void reverseDfs(State v):
v.canReach = true
for each State u in v.prev:
if !u.canReach:
reverseDfs(u)
boolean dfs(State v): // returns true if and only if there is a cycle
v.color = GREY
for each State u in v.next:
if u.color == GREY:
return true
if u.canReach && u.color == WHITE && dfs(u):
return true
v.color = BLACK
return false
int words(Automaton a):
for each State v in a:
v.canReach = false
for each State v in a:
if v.isFinal:
reverseDfs(v)
for each State v in a:
v.color = WHITE
if dfs(a.start):
return infinity
Stack sorted = topSort(a)
paths = new int[a.statesNumber]
fill(paths, 0)
paths[0] = 1
while !sorted.isEmpty:
State v = sorted.pop()
for each State u in v.next:
paths[u] += paths[v]
int result = 0
for each State v in a:
if v.isFinal:
result += paths[v]
return result
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177: ISBN 5-8459-0261-4 (рус.)
Примечания