418
правок
Изменения
Нет описания правки
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.
== Псевдокод ==
Функция для построения списка обратных ребер.
'''vector'''[][] buildReverseEdges('''int''' n, '''int'''[][] <tex>\delta</tex>):
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
<tex>\delta^{-1}</tex>[<tex>\delta</tex>[i][c]][c].add(i)
Функция для проверки достижимости состояний.
'''function''' checkReachability('''int''' u, '''boolean'''[] visited):
visited[u] = true;
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
if '''not''' visited[<tex>\delta</tex>[u][c]]
checkReachability(<tex>\delta</tex>[u][c], visited)
Функция для инициализации таблицы неэквивалентности.
'''function''' initTable('''int''' n, '''boolean'''[] isTerminal, '''queue''' Q, '''boolean'''[][] table):
for i = 0 .. n - 1
for j = 0 .. n - 1
if '''not''' table[i][j] '''and''' isTerminals[i] '''and''' '''not''' isTerminals[j] '''and''' i != j
table[i][j] = table[j][i] = true
Q.push(<tex>\langle i, j \rangle</tex>)
==Асимптотики==
