418
правок
Изменения
м
==Постановка задачи==
Функция для вычисления таблицы неэквивалентности. '''function''' computeTable('''int''' n, '''list'''[][] <texfont color="green">\delta^{-1}// Шаг 4</texfont>, '''queue''' Q, '''boolean'''[][] marked):
Нет описания правки
{{Задача
|definition =
== Псевдокод ==
Функция для инициализации построения таблицы неэквивалентности. '''function''' initTablebuildTable('''int''' n, '''boolean'''[] isTerminal, '''vector'''[][] <tex>\delta^{-1}</tex>, '''queue''' Q, '''boolean'''[][] marked): <font color="green">// Шаг 3</font>
'''for''' i = 0 .. n - 1
'''for''' j = 0 .. n - 1
marked[i][j] = marked[j][i] = true
Q.push(<tex>\langle i, j \rangle</tex>)
'''while''' '''not''' Q.isEmpty()
<tex>\langle u, v \rangle</tex> = Q.poll()
'''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
<font color="green">// Шаг 1</font>
'''listvector'''[][] <tex>\delta^{-1}</tex> = buildReverseEdges(n, <tex>\delta</tex>) <font color="green">// Cтроим список обратных ребер.</font>
<font color="green">// Шаг 2</font>
'''boolean''' reachable[n]
checkReachability(1, reachable) <font color="green">// Cтроим таблицу достижимости состояний.</font>
<font color="green">// Шаг Шаги 3и 4</font>
'''queue''' Q
'''boolean''' marked[n][n] initTablemarked = buildTable(n, isTerminal, Q, marked) <font color="green"tex>// Шаг 4\delta^{-1}</fonttex>, Q, marked)
computeTable(n, <tex>\delta^{-1}</tex>, Q, marked)
<font color="green">// Шаг 5</font>
