171
правка
Изменения
Нет описания правки
==== Псевдокод ====
void revDfsreverseDfs(State v): v.seen canReach = true
for each State u in v.prev:
if !u.seencanReach: revDfsreverseDfs(u)
void setSink(Automaton a):
sink.next(c) = sink
for each State v in a:
if !v.seencanReach:
v = sink
void bfs(Automaton a, Automaton b) eq = new bool, boolean[a.statesNumber][b.statesNumber]eq)
fill(eq, false)
eq[a.start][b.start] = true
boolean areEqual(Automaton a, Automaton b)
for each State v in a:
v.seen canReach = false
for each State v in a:
if v.isFinal:
setSink(a)
for each State v in b:
v.seen canReach = false
for each State v in b:
if v.isFinal:
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:
return false
return true
== Конечность языка, подсчёт числа слов ==
Язык называется '''конечным''', если принадлежащее ему множество слов конечно.
{{Утверждение
|id=
regFinite
|statement=
Автомат <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{1}</tex> не существует состояния <tex>v</tex>, для которого выполняются три условия:
1) <tex>v</tex> достижимо из стартового состояния <tex>s</tex>;
2) из <tex>v</tex> достижимо какое-либо из допускающих состояний;
3) из <tex>v</tex> по одному или более переходам достижимо <tex>v</tex>.
|proof=
Пусть такое состояние <tex>v</tex> существует, а строки <tex>x, y, z</tex> таковы, что <tex>\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle</tex>, <tex>t</tex> - допускающее, <tex>y</tex> - непустая. Рассмотрим строки вида <tex>xy^{k}z, k \in \mathbb{N}</tex>. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено <tex>n! (n-1)^{| \Sigma |}</tex>, где <tex>n</tex> - количество состояний автомата: <tex>n!</tex> - количество перестановок состояний, <tex>(n-1)^{| \Sigma |}</tex> - количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
}}
=== Алгоритм нахождения числа слов в языке ===
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим ''полезные'' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>paths(v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>paths(s) = 1</tex>. Заметим, что если известны значения <tex>paths(u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>paths(v) = \sum\limits_{u}paths(u)</tex>. Количеством слов в языке будет сумма <tex>paths(t)</tex> для всех допускающих <tex>t</tex>.
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.
==== Псевдокод ====
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 iff 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
