418
правок
Изменения
м
'''vector'''[][] Построим таблицу списков обратных ребер - <tex>\delta^{-1}</tex> = buildReverseEdges(n, размером <tex>n \deltatimes n</tex>) <font color="green">// Cтроим список обратных ребер.</font>
'''boolean''' reachable[n] checkReachability(1, Построим массив достижимости состояний из стартового - reachable) размером <font color="green"tex>// Cтроим таблицу достижимости состояний.n</fonttex>.
→Псевдокод
'''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
<font color="green">// Шаг 1</font>
<font color="green">// Шаг 2</font>
<font color="green">// Шаги 3 и 4</font>
'''boolean'''[][] marked = buildTable(n, isTerminal, <tex>\delta^{-1}</tex>)
'''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font>
fill(component, -1)
'''listvector''' classes <font color="green">// По позиции i будем хранить представителя i-ой компоненты эквивалентности.</font>
'''for''' i = 0 .. n - 1
'''if''' '''not''' table[0][i]
component[j] = components_count
<font color="green">// Шаг 6</font>
buildDFA(reachable, classes, component) <font color="green">// Строим по классам эквивалентности требуемый автомат.</font>
==Асимптотика==
