Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
==== Псевдокод ====
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)
== Совпадение регулярных языков ==
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они разделены.
==== Псевдокод ====
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
== Литература ==
