211
правок
Изменения
→Алгоритм
==Алгоритм==
Основная идея алгоритма заключается в том, чтобы разбить состояния на классы эквивалентности — они и будут состояниями минимального автомата. <br>
Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. <br>
Будем помечать в таблице пары неэквивалентных состояний и класть их в очередь. <br>
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</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>
