Изменения
→Алгоритм
==Алгоритм==
Основная идея алгоритма разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата.<br>В таблице Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата будем . <br>Будем помечать неэквивалентные состоянияв таблице пары неэквивалентных состояний и класть их в очередь.<br>
Изначально добавим в очередь <tex>Q</tex> пары состояний различимых строкой <tex> \varepsilon </tex> и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</tex>.
#Для всех пар <tex> \langle t, k \rangle </tex>, таких, что <tex> \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle </tex> и пара <tex> \langle t, k \rangle</tex> не отмечена в таблице, то отметим ее в таблице и добавим в <tex>Q</tex>.На момент опустошения очереди, пары состояний, не помеченных в таблице, являются парами эквивалентных состояний. За один проход по таблице , согласно теореме , разбиваем не помеченные состояния пары эквивалентных состояний на классы эквивалентности. <br>
Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата. <br>
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.
