Изменения
Нет описания правки
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (их можно различить любой строкой начинающейся с символа <tex>a</tex>). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.
Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний и класс недопускающих состояний.
# Оба этих класса помещаются в очередь.
# Из очереди извлекается класс, далее именуемый как сплиттер.
# Перебираются все символы из алфавита <tex>\Sigma</tex>, где <tex>a</tex> {{---}} текущий символ.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.6.
===Псевдокод===
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. <br/>
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. <br/>
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}
===Псевдокод===
<tex>W</tex>.pop(<tex>S</tex>)
for all <tex>a \in \Sigma</tex>
for all each <tex>R</tex> in <tex>P</tex> split by <tex>R_1 = R \cap \delta^{-1} (S, a) </tex> <tex>R_2 = R \setminus R_1</tex> if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex> replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex> if <tex>R</tex> in <tex>W</tex> replace <tex>R</tex> in <tex>W</tex> with <tex>R_1</tex> and <tex>R_2</tex> else if <tex> |R_1| \le |R_2|</tex> <tex>W</tex>.push(<tex>R_1</tex>) else <tex>W</tex>.push(<tex>R_2</tex>)=Корректность алгоритма=
=Время работы алгоритма=
Благодаря системе добавления классов состояний в очередь, каждое ребро будет рассмотрено не более чем <tex>\log{n}</tex> раз. А так как ребер у нас порядка <tex> |\Sigma| * n </tex> то получаем <tex> O(n\log{n})</tex>
