172
правки
Изменения
→Псевдокод
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</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 all <tex>a \in \Sigma</tex> for all <tex>R</tex> in <tex>P</tex> <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> <tex>W</tex>.push(<tex>R_1</tex>) <tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
