418
правок
Изменения
→Описание
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь. Изначально добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.Пока <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>0</tex>, в которую будут вести по умолчанию все переходы по всем символам, которых ещё не было в исходном автомате. Теперь стартовое состояние будет иметь номер <tex>1</tex>.
* '''Шаг 1'''. Построим множество <tex>\delta^{-1}</tex>, в котором будем хранить списки обратных ребер.
* '''Шаг 2'''. Найдем все достижимые состояния из стартового.
* '''Шаг 3'''. Добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.
* '''Шаг 4'''. Для каждой непомеченной пары <tex> \langle u, v \rangle </tex> нужно проверить, что <tex>\mathcal {9} c \in \Sigma</tex> такой, что пара <tex>\langle \delta(u, c), \delta(v, c) \rangle</tex> помечена. Тогда мы можем пометить пару <tex> \langle u, v \rangle </tex>.
: Пока <tex>Q</tex> не станет пуста, будем делать следующее:
: 1. Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</tex>.
: 2. Для каждого символа <tex>c \in \Sigma</tex> перебираем пары состояний <tex>\langle \delta^{-1}(u, c), \delta^{-1}(v,c) \rangle</tex>. Если находим ещё непомеченную пару, то помечаем её в таблице и кладем в очередь.
: В момент опустошения очереди пары состояний, не помеченные в таблице, являются парами эквивалентных состояний.
* '''Шаг 5'''. За один проход по таблице разбиваем пары эквивалентных состояний на классы эквивалентности.
* '''Шаг 6'''. За один проход по списку классов эквивалентности выделяем список новых состояний и переходов между ними.
Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата.
