142
правки
Изменения
Нет описания правки
= Минимизация ДКА =
Понятие [[ Эквивалентность_состояний_ДКА | эквивалентности состояний]] позволяет объединить состояния в блоки классы следующим образом.# Все состояния в блоке классе эквивалентны.# Любые два состояния, выбранные из разных блоковкласов, неэквивалентны.Таким образом, основная идея минимизации ДКА состоит в разбиении множества состояний на блоки классы эквивалентности.
===Пример минимизации ДКА===
[[Изображение:Automaton1.png]][[Изображение:Automaton2.png]]
Первый блок класс состоит из состояния <tex>A</tex>, а второй из эквивалентных состояний <tex>B</tex> и <tex>C</tex>.
= Алгоритм =
Алгоритм итеративно строит разбиение множества состояний следующим образом.
<tex>W \leftarrow \{ F, Q \setminus F \}</tex>
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not isEmpty(<tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S</tex>)
for all <tex>a \in \Sigma</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>
if <tex> |R_1| \le |R_2|</tex>
