Изменения

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

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

117 байт убрано, 14:21, 4 ноября 2013
→‎Псевдокод
<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>F, a</tex>) else '''for allmin''' (<tex>a F, Q \in \Sigmasetminus F</tex> <tex>W</tex>'''.push'''(), <tex>Q \setminus F, a</tex>)
'''while not''' <tex>W</tex>'''.isEmpty()'''
<tex>W</tex>'''.pop'''(<tex>S, a</tex>)
'''for each''' <tex>R</tex> '''in''' <tex>P</tex> '''split by''' <tex>(S, a)</tex>
'''replace''' <tex>R</tex> '''in''' <tex>P</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
'''if''' (<tex>R, a</tex>) '''in''' <tex>W</tex>
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/33376»

Навигация