Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) — различия между версиями
Строка 3: | Строка 3: | ||
= Алгоритм = | = Алгоритм = | ||
− | Основная идея минимизации состоит в разделении состояний ДКА | + | Основная идея минимизации состоит в разделении состояний ДКА на классы эквивалентности. Получившиеся классы и будут состояниями минимального автомата. |
===Разбиения на блоки=== | ===Разбиения на блоки=== | ||
− | Пусть <tex>Q</tex> {{---}} множество состояний ДКА. Разделим <tex>Q</tex> на 2 | + | Пусть <tex>Q</tex> {{---}} множество состояний ДКА. Разделим <tex>Q</tex> на 2 класса <tex>F</tex> и <tex>Q \setminus F</tex>, где <tex>F</tex> {{---}} множество терминальных состояний и <tex>Q \setminus F</tex> {{---}} множество нетерминальных состояний. Теперь будем делить классы до тех пор, пока они не будут содержать только эквивалентные состояния. Для этого создадим множество сплиттеров, где сплиттер {{---}} это множество состояний. Для каждой буквы <tex>a</tex> из алфавита <tex>\Sigma</tex> создадим множество <tex>l_a</tex>, состоящее из состояний имеющих ребро в текущий сплиттер по букве <tex>a</tex>. Если какой-нибудь класс имеет не нулевое пересечение с <tex>l_a</tex>, а также не является его подмножеством, то его можно разделить на два новых класса. Первый класс состоит из состояний, которые имеют ребра в текущий сплиттер по букве <tex>a</tex>, а второй класс состоит из оставшихся состояний. Меньший из них добавим в множество сплиттеров <tex>W</tex> и обновим множество блоков <tex>P</tex>. Продолжаем деление до тех пор пока множество сплиттеров не пусто. |
===Псевдокод=== | ===Псевдокод=== |
Версия 04:26, 7 ноября 2011
Содержание
Постановка задачи
Пусть дан автомат распознающий определенный язык. Требуется найти автомат с наименьшим количеством состояний, который распознает этот же язык.
Алгоритм
Основная идея минимизации состоит в разделении состояний ДКА на классы эквивалентности. Получившиеся классы и будут состояниями минимального автомата.
Разбиения на блоки
Пусть
— множество состояний ДКА. Разделим на 2 класса и , где — множество терминальных состояний и — множество нетерминальных состояний. Теперь будем делить классы до тех пор, пока они не будут содержать только эквивалентные состояния. Для этого создадим множество сплиттеров, где сплиттер — это множество состояний. Для каждой буквы из алфавита создадим множество , состоящее из состояний имеющих ребро в текущий сплиттер по букве . Если какой-нибудь класс имеет не нулевое пересечение с , а также не является его подмножеством, то его можно разделить на два новых класса. Первый класс состоит из состояний, которые имеют ребра в текущий сплиттер по букве , а второй класс состоит из оставшихся состояний. Меньший из них добавим в множество сплиттеров и обновим множество блоков . Продолжаем деление до тех пор пока множество сплиттеров не пусто.Псевдокод
— множество сплиттеров. — множество всех блоков ДКА.
while is not empty do select and remove from for all do for all in and do partition into and and replace in with and if then replace in with and else if then add to else add to
Время работы алгоритма
Благодаря системе добавления множеств состояний в множество сплиттеров, каждое ребро будет рассмотрено не более чем
раз. А так как ребер у нас порядка то получаемЛитература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
- J. E. Hopcroft. — An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-71-190, Stanford University, January 1971.