Изменения

Пусть <tex>Q</tex> {{- --}} множество состояний ДКА. Разделим <tex>Q</tex> на 2 блока <tex>F</tex> и <tex>Q - \setminus F</tex>, где <tex>F</tex> {{--- }} множество терминальных состояний и <tex>Q - \setminus F</tex>{{--- }} множество нетерминальных состояний. Теперь будем делить блоки до тех пор, пока они не будут содержать только эквивалентные состояния. Для этого создадим множество сплитеровсплиттеров, где сплитер сплиттер {{--- }} это множество состояний. Для каждой буквы <tex>a</tex> из алфавита <tex>\Sigma</tex> создадим множество <tex>l_a</tex>, состоящее из состояний имеющих ребро в текущий сплитер сплиттер по букве <tex>a</tex>. Если какой-нибудь блок имеет не нулевое пересечение с <tex>l_a</tex>, а также не является его подмножеством, то его можно разделить на два новых блока. Первый блок состоит из состояний, которые имеют ребра в текущий сплитер сплиттер по букве <tex>a</tex>, а второй блок состоит из оставшихся состояний. Меньший из них добавим в множество сплитеров сплиттеров <tex>W</tex> и обновим множество блоков <tex>P</tex>. Продолжаем деление до тех пор пока множество сплитеров сплиттеров не пусто.

<tex>W</tex> {{---}} множество сплитеровсплиттеров.

<tex>W \leftarrow \{ F, Q - \setminus F \}</tex> <tex>P \leftarrow \{ F, Q - \setminus F \}</tex>

Благодаря системе добавления множеств состояний в множество сплитеровсплиттеров, каждое ребро будет рассмотрено не более чем <tex>\log{n}</tex> раз. А так как ребер у нас порядка <tex> |\Sigma| * n </tex> то получаем <tex> O(n\log{n})</tex>