Изменения

Перейти к: навигация, поиск

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

Нет изменений в размере, 20:04, 15 января 2013
Псевдокод
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
'''if''' <tex> |F| \le |Q \setminus F|</tex>
'''for all''' <tex>a \in \Sigma</tex>
<tex>W</tex>'''.push'''(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
'''while not''' <tex>W</tex>'''.isEmpty()'''
<tex>W</tex>'''.pop'''(<tex>S, a</tex>)
Анонимный участник

Навигация