418
правок
Изменения
→Псевдокод
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>)
Функция для вычисления таблицы неэквивалентности.
'''function''' computeTable('''int''' n, '''int'''[][] <tex>\delta^{-1}</tex>, '''queue''' Q, '''boolean'''[][] table):
'''while''' '''not''' Q.isEmpty()
<tex>\langle u, v \rangle</tex> = Q.poll()
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
'''list''' rr = <tex>\delta^{-1}</tex>[u][c]
'''list''' ss = <tex>\delta^{-1}</tex>[v][c]
'''for''' i = 0 .. length(rr) - 1
'''int''' r = rr[i]
'''for''' j = 0 .. length(ss) - 1
'''int''' s = ss[j]
'''if''' '''not''' table[r][s]
table[r][s] = table[s][r] = true
Q.push(<tex>\langle r, s \rangle</tex>)
==Асимптотики==
