Изменения

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

Алгоритм Хопкрофта

111 байт убрано, 11:44, 8 декабря 2013
Псевдокод
<tex>insert \ (min(R_1, R_2), c)</tex> '''to''' <tex>S</tex>
К сожалению, совсем не очевидно, как быстро находить множество <tex>T</tex>. С другой стороны, понятно, что <tex>T\subset T'</tex>, где <tex>T'</tex> {{---}} это подмножество множество классов текущего разбиения, из состояний которых в ДКА автомате существует переход в сплиттер состояния сплиттера <tex>C</tex> по символу <tex>a</tex>. Пусть <tex>Inverse = \{r \ | \ r \in Q, \ \delta(r, a) \in C\}</tex>, а <tex>T' = \{R \ | \ R \in P, \ R \cap Inverse \neq \varnothing\}</tex>. Тогда <tex> T \subset T'</tex>.
Модифицируем наш алгоритм: для каждой очередной пары <tex> (C, a) </tex> будем находить <tex> T' </tex>, и с каждым классом состояний из <tex> T' </tex> будем производить те же действия, что и раньше.
403
правки

Навигация