1
правка
Изменения
можно было догадаться, тем не менее, не было очевидно, что это имеется в виду
Для реализации алгоритма нам потребуются [[Очередь | очередь]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА | неэквивалентных состояний]] и класть их в очередь.
* В исходном автомате мы имели <tex>n</tex> состояний с номерами от <tex>0</tex> до <tex>n - 1</tex>. Удобно будет увеличить все номера состояний на <tex>1</tex> и добавить в исходный автомат вершину <tex>0</tex>, в которую будут вести по умолчанию все переходы по всем символам(в том числе переходы по всем символам в эту вершину из неё самой), которых ещё не было в исходном автомате, тем самым увеличив количество состояний <tex>n</tex> на <tex>1</tex>. Теперь стартовое состояние будет иметь номер <tex>1</tex>.
* '''Шаг 1'''. Построим множество <tex>\delta^{-1}</tex>, в котором будем хранить списки обратных ребер.
* '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин | обхода в глубину]].
'''boolean''' marked[n][n]
<font color="green">// Шаг 3</font>
'''for''' i = 0 .. <tex>\ldots</tex>n - 1 '''for''' j = 0 .. <tex>\ldots</tex>n - 1
'''if''' '''not''' marked[i][j] '''and''' isTerminal[i] != isTerminal[j]
marked[i][j] = marked[j][i] = ''true''
'''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font>
fill(component, -1)
'''for''' i = 0<tex>\ldots </tex>n - 1
'''if''' '''not''' marked[0][i]
component[i] = 0
'''int''' componentsCount = 0
'''for''' i = 1<tex>\ldots </tex>n - 1
'''if''' '''not''' reachable[i]
''continue''
componentsCount++
component[i] = componentsCount
'''for''' j = i + 1<tex>\ldots </tex>n - 1
'''if''' '''not''' marked[i][j]
component[j] = componentsCount
=== Шаг <tex> 5 </tex> ===
Из таблицы видно, что классы эквивалентных состояний это <tex> \mathcal {f} A, B \mathcal {g}, \mathcal {f} C, D \mathcal {g}, \mathcal {f} F, G \mathcal {g}, \mathcal {f} E \mathcal {g}, \mathcal {f} H \mathcal {g} </tex>.
=== Шаг <tex> 6 </tex> ===
