Изменения
Нет описания правки
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс не может быть разбитневозможно разбить.
= Алгоритм Хопкрофта=
{{Лемма|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.|proof = Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or :<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> :<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>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or :<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> :<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.}}
Алгорит Хопкрофта является улучшением простого алгоритма.
