200
правок
Изменения
м
Нет описания правки
{{Задача
|definition =
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
}}
==Алгоритм==
=== Описание ===
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
Для реализации алгоритма нам потребуются [[Очередь|очередь]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь.
* В исходном автомате мы имели <tex>n</tex> состояний с номерами от <tex>0</tex> до <tex>n - 1</tex>. Удобно будет увеличить все номера состояний на <tex>1</tex> и добавить в исходный автомат вершину <tex>0</tex>, в которую будут вести по умолчанию все переходы по всем символам, которых ещё не было в исходном автомате, тем самым увеличив количество состояний <tex>n</tex> на <tex>1</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>\mathcal{O}(n \cdot |\Sigma|)</tex> времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>\mathcal{O}(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>\mathcal{O}(n^2)</tex>.
==Пример работы==
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
* [[wikipedia:ru:DFA_minimization|Wikipedia {{---}} DFA minimization]]
* [http://www.eecs.berkeley.edu/~sseshia/172/lectures/Lecture6.pdf Sanjit A. Seshia, "Minimization of DFAs"]
* [http://www.comp.nus.edu.sg/~cs4212/dfa-min.pdf National University of Singapore, "DFA Minimization"]
