В теории автоматов (раздел теоретической информатики ) минимизация DFA - это задача преобразования данного детерминированного конечного автомата (DFA) в эквивалентный DFA, который имеет минимальное количество состояний. Здесь два DFA называются эквивалентными, если они распознают один и тот же обычный язык . Известно несколько различных алгоритмов, решающих эту задачу, и они описаны в стандартных учебниках по теории автоматов. [1]
Минимальный DFA
Для каждого регулярного языка также существует минимальный автомат, который его принимает, то есть DFA с минимальным количеством состояний, и этот DFA уникален (за исключением того, что состояниям можно давать разные имена). [2] [3] Минимальный DFA обеспечивает минимальные вычислительные затраты для таких задач, как сопоставление с образцом .
Есть два класса состояний, которые можно удалить или объединить из исходного DFA, не влияя на язык, который он принимает.
- Недостижимые состояния - это состояния, которые недоступны из начального состояния DFA для любой входной строки. Эти состояния можно удалить.
- Мертвые состояния - это состояния, из которых невозможно достичь конечного состояния. Эти состояния могут быть удалены, если автомат не требует полной комплектации .
- Неразличимые состояния - это состояния , которые нельзя отличить друг от друга ни для одной входной строки. Эти состояния можно объединить.
Минимизация DFA обычно выполняется в три этапа:
- удалить мертвые и недоступные состояния (это ускорит следующий шаг),
- объединить неотличимые состояния,
- при желании можно воссоздать единичное мертвое состояние (состояние "приемник"), если требуется, чтобы результирующий DFA был полным.
Недостижимые состояния
Штат детерминированного конечного автомата недостижим, если нет строки в существует для которого . В этом определении это множество состояний, - набор входных символов, - функция перехода (отображение состояния и входного символа в набор состояний), это его расширение до строк (также известное как расширенная функция перехода), - начальное состояние, а - это набор принимающих (также называемых конечных) состояний. Достижимые состояния могут быть получены по следующему алгоритму:
пусть reachable_states : = { q0 }; пусть new_states : = { q0 };делать { темп : = в пустой набор ; для каждого q в new_states do для каждого c в Σ do temp : = temp ∪ { p такое, что p = δ ( q , c )}; конец ; конец ; new_states : = temp \ reachable_states ; reachable_states : = reachable_states ∪ new_states ; } В то время как ( new_states ≠ пустым набора ); unreachable_states : = Q \ reachable_states ;
Предполагая эффективную реализацию наборов (например new_states
) и операций над ними (таких как добавление состояния или проверка его наличия), этот алгоритм может быть реализован с временной сложностью., где количество состояний и - количество переходов входного автомата.
Недостижимые состояния можно удалить из DFA, не влияя на поддерживаемый язык.
Неотличимые состояния
Следующие алгоритмы представляют различные подходы к слиянию неотличимых состояний.
Алгоритм Хопкрофта
Один из алгоритмов слияния неотличимых состояний DFA, предложенный Хопкрофтом (1971) , основан на уточнении разбиения, разбиении состояний DFA на группы по их поведению. Эти группы представляют собой классы эквивалентности на Myhill-Nerode отношением эквивалентности , причем каждые два состояния одного и того же раздела являются эквивалентными , если они имеют одинаковое поведение для всех входных последовательностей. То есть для каждых двух состояний p 1 и p 2, которые принадлежат одному и тому же классу эквивалентности в разделе P , и каждого входного слова w , переходы, определяемые w, всегда должны переводить состояния p 1 и p 2 в равные состояния, утверждает, что оба принимают или заявляют, что оба отвергают. Для w не должно быть возможности перевести p 1 в состояние приема, а p 2 в состояние отклонения или наоборот.
Следующий псевдокод описывает алгоритм:
P : = { F , Q \ F }; W : = { F , Q \ F }; в то время как ( W это не пусто ) делать выбор и удалить в набор A из W для каждого с в Е у пусть Х будет множество из состояний для которого переход от гр приводит к в состояние , в A для каждого множества Y в P для которого Х ∩ Y является непустым и Y \ X является непустой ли заменить Y в P на тех двух множеств X ∩ Y и Y \ X , если Y является в W заменить Y в W на тех же двух множеств либо еще , если это | X ∩ Y | <= | Y \ X | добавить X ∩ Y к W иначе добавить Y \ X к W end ; конец ; конец ;
Алгоритм начинается с слишком грубого разбиения: каждая пара состояний, эквивалентных согласно соотношению Майхилла – Нероде, принадлежит одному и тому же набору в разбиении, но неэквивалентные пары также могут принадлежать одному и тому же набору. Он постепенно уточняет разбиение на большее количество меньших наборов, на каждом шаге разбивая наборы состояний на пары подмножеств, которые обязательно неэквивалентны. Начальное разделение - это разделение состояний на два подмножества состояний, которые явно не имеют такого же поведения, как друг друга: принимающие состояния и отклоняющие состояния. Затем алгоритм несколько раз выбирает набор A из текущего раздела и входного символа c и разбивает каждый из наборов раздела на два (возможно, пустые) подмножества: подмножество состояний, которые приводят к A на входном символе c , и подмножество состояний , которые не приводят к А . Так уже известно, имеют различное поведение , чем другие наборы разбиения, подмножество , которые приводят к А также иметь различное поведение , чем подмножества , которые не приводят к А . Когда больше не удается найти разбиения этого типа, алгоритм завершается.
Лемма . Учитывая фиксированный символ c и класс эквивалентности Y, который разбивается на классы эквивалентности B и C, только один из B или C необходим для уточнения всего разбиения. [4]
Пример: предположим, что у нас есть класс эквивалентности Y, который разбивается на классы эквивалентности B и C. Предположим, у нас также есть классы D, E и F; D и E имеют состояния с переходами в B на символе c, в то время как F имеет переходы в C на символе c. По лемме мы можем выбрать либо B, либо C в качестве отличителя, скажем B. Тогда состояния D и E разделяются их переходами в B. Но F, который не указывает на B, просто не разделяется во время текущей итерации алгоритма; он будет уточнен другими отличителями.
Наблюдение . Все B или C необходимы для правильного разделения ссылающихся классов, таких как D, E и F - подмножества не подходят.
Цель самого внешнего оператора if ( если Y находится в W ) состоит в том, чтобы исправить W, набор отличительных признаков. В предыдущем утверждении алгоритма мы видим, что Y только что разделен. Если Y находится в W, он просто устарел как средство разделения классов в будущих итерациях. Таким образом, Y необходимо заменить обоими расщеплениями из-за наблюдения выше. Однако, если Y не входит в W, только одно из двух разбиений, а не оба, необходимо добавить к W из-за леммы выше. Выбор меньшего из двух разбиений гарантирует, что новое добавление к W будет не более половины размера Y; это ядро алгоритма Хопкрофта: как он получает свою скорость, как объясняется в следующем абзаце.
Худшем случае время работы этого алгоритма O ( нс войти п ) , где п есть число состояний и S является размером алфавита. Эта оценка следует из того факта, что для каждого из ns переходов автомата наборы, взятые из Q, которые содержат целевое состояние перехода, имеют размеры, уменьшающиеся друг относительно друга в два или более раз, поэтому каждый переход участвует в O (log n ) этапах расщепления в алгоритме. Структура данных уточнения раздела позволяет выполнять каждый шаг разделения во времени, пропорциональном количеству переходов, которые в нем участвуют. [5] Это остается наиболее эффективным известным алгоритмом для решения проблемы, а для некоторых распределений входных данных его средняя сложность даже лучше, O ( n log log n ) . [6]
После того, как алгоритм Хопкрофта был использован для группировки состояний входного DFA в классы эквивалентности, минимальный DFA может быть построен путем формирования одного состояния для каждого класса эквивалентности. Если S - это набор состояний в P , s - это состояние в S , а c - входной символ, то переход в минимальном DFA из состояния для S на входе c переходит в набор, содержащий состояние, которое входной автомат перейдет из состояния s на вход c . Начальное состояние минимального DFA - это то, которое содержит начальное состояние входного DFA, а принимающие состояния минимального DFA - это те, члены которых принимают состояния входного DFA.
Алгоритм Мура
Алгоритм Мура для минимизации DFA разработан Эдвардом Ф. Муром ( 1956 ). Подобно алгоритму Хопкрофта, он поддерживает раздел, который начинается с отделения состояний принятия от состояний отклонения, и многократно уточняет раздел до тех пор, пока дальнейшие уточнения не станут невозможными. На каждом шаге, он заменяет текущий раздел с грубым общим уточнением из з + 1 разделов, один из которых является текущей и другими являются прообразами текущего раздела под функциями перехода для каждого из входных символов. Алгоритм завершается, когда эта замена не изменяет текущий раздел. Его временная сложность в наихудшем случае составляет O ( n 2 с ) : каждый шаг алгоритма может быть выполнен за время O ( нс ) с использованием варианта сортировки по основанию для изменения порядка состояний так, чтобы состояния в том же наборе нового раздела были в порядке следования, и существует не более n шагов, поскольку каждый, кроме последнего, увеличивает количество наборов в разделе. Примеры проблемы минимизации DFA, которые вызывают наихудшее поведение, такие же, как для алгоритма Хопкрофта. Количество шагов, которые выполняет алгоритм, может быть намного меньше n , поэтому в среднем (для константы s ) его производительность составляет O ( n log n ) или даже O ( n log log n ) в зависимости от случайного распределения автоматов, выбранных для моделировать поведение алгоритма в среднем случае. [6] [7]
Алгоритм Бжозовского
Обращение переходов недетерминированного конечного автомата (NFA)и переключение начального и конечного состояний [примечание 1] создает NFAдля обращения к исходному языку. Преобразование этого NFA в DFA с использованием стандартной конструкции powerset (с сохранением только достижимых состояний преобразованного DFA) приводит к DFAдля того же обратного языка. Как заметил Бжозовский (1963) , повторение этого обращения и детерминации во второй раз, снова сохраняя только достижимые состояния, дает минимальный DFA для исходного языка.
Интуиция, лежащая в основе алгоритма, такова: определение обратного автомата объединяет состояния, которые неотличимы в исходном автомате, но могут объединять также состояния, которые не должны объединяться (т. Е. Не объединяются в минимальном DFA). В таком случае после того, как мы перевернем автомат во второй раз, он может оказаться недетерминированным. Поэтому нам нужно снова его определить, получив минимальный DFA.
Доказательство правильности
После того, как мы определим чтобы получить , мы изменим это чтобы получить . Сейчас имеет тот же язык, что и , но есть одно важное отличие: в из которого мы можем принять то же слово. Это следует избыть детерминированным, а именно. в, которого мы можем достичь из начального состояния через то же слово. Детерминирование затем создает состояния власти (наборы состояний ), где каждые два состояния различаются - естественно - хотя бы в одном состоянии из . Предполагать а также ; тогдадобавляет хотя бы одно слово [примечание 2] к языку[примечание 3], которые не могли присутствовать в, поскольку это слово уникально для (ни одно другое государство его не принимает). Мы видим, что это справедливо для каждой пары состояний власти, и, таким образом, каждое состояние власти отличается от любого другого состояния власти. Следовательно, после определения, у нас есть DFA без неразличимых или недостижимых состояний; следовательно, минимальный DFA для оригинала .
Если уже детерминирован, тогда достаточно его обрезать, [примечание 4] перевернуть, детерминировать и затем снова перевернуть. Это можно рассматривать как начало св приведенном выше процессе (при условии, что он уже был обрезан), поскольку входной FA уже детерминирован (но имейте в виду, что на самом деле это не реверсирование). Мы переворачиваем и определяем чтобы получить , который является минимальным DFA для обращения языка(поскольку мы пока сделали только один разворот). Теперь все, что осталось сделать, это повернуть вспять чтобы получить минимальный DFA для исходного языка.
Сложность
Наихудшая сложность алгоритма Бжозовского экспоненциально зависит от числа состояний входного автомата. Это выполняется независимо от того, является ли вход NFA или DFA. В случае DFA экспоненциальный взрыв может произойти при детерминировании разворота входного автомата; [примечание 5] в случае NFA это также может произойти во время первоначального определения входного автомата. [примечание 6] Однако алгоритм часто работает лучше, чем можно было бы предположить в этом наихудшем случае. [6]
Минимизация NFA
Хотя описанные выше процедуры работают для DFA, метод разделения не работает для недетерминированных конечных автоматов (NFA). [8] Хотя исчерпывающий поиск может минимизировать NFA, не существует алгоритма полиномиального времени для минимизации общих NFA, если только P = PSPACE , нерешенная гипотеза в теории вычислительной сложности, которая, как многие полагают, неверна. Однако есть методы минимизации NFA, которые могут быть более эффективными, чем перебор. [9]
Смотрите также
Заметки
- ^ Хопкрофт Motwani и Ульман (2001) , раздел 4.4.3, "Минимизация ДКИ".
- ↑ Hopcroft & Ullman (1979) , раздел 3.4, теорема 3.10, стр.67
- ^ Хопкрофт, Мотвани и Ульман (2001) , раздел 4.4.3, «Минимизация DFA», стр. 159, и стр. 164 (замечание после теоремы 4.26)
- ^ На основании следствия 10 Knuutila (2001)
- ^ Хопкрофт (1971) ; Ахо, Хопкрофт и Ульман (1974)
- ^ a b c Berstel et al. (2010) .
- ^ Дэвид (2012) .
- ↑ Hopcroft, Motwani & Ullman (2001) , раздел 4.4, рисунок с пометкой «Минимизация состояний NFA», стр. 163.
- ^ Kameda & Weiner (1970) .
- ^ В случае, если есть несколько конечных состояний в M, мы либо должны разрешить несколько начальных состояний в обращении M; или добавить дополнительное состояние с ε-переходами ко всем начальным состояниям и сделать только это новое состояние начальным.
- ^ Напомним, что в M 'нет мертвых состояний; таким образом, по крайней мере одно слово принимается от каждого штата.
- ^ Язык государства - это набор слов, принятых из этого состояния.
- ^ Trim = удалить недостижимые и мертвые состояния.
- ^ Например, язык двоичных строк, у которых n- й символ является единицей, требует только n + 1 состояния, но его обращение требует 2 n состояний. Leiss (1981) дает трехкомпонентный п -ему государственному DFA которого требует разворот 2 п состояния, максимально возможного. Дополнительные примеры и наблюдение связи между этими примерами и наихудшим анализом алгоритма Бжозовского см. В Câmpeanu et al. (2001) .
- ^ Экспоненциальный взрыв произойдет не более одного раза, а не в обеих детерминизациях. То есть алгоритм в худшем случае экспоненциальный, а не дважды экспоненциальный.
Рекомендации
- Ахо, Альфред В .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974), «4.13 Разделение», Дизайн и анализ компьютерных алгоритмов , Addison-Wesley, стр. 157–162.
- Берстель, Жан; Боассон, Люк; Картон, Оливье; Фагно, Изабель (2010), «Минимизация автоматов», « Автоматы: от математики к приложениям» , Европейское математическое общество, arXiv : 1010.5318 , Bibcode : 2010arXiv1010.5318B
- Brzozowski, JA (1963), "Канонические регулярные выражения и минимальные графы состояний для определенных событий", Proc. Симпозиумы. Математика. Теория автоматов (Нью-Йорк, 1962) , Политехническая пресса Политехнического института. of Brooklyn, Brooklyn, NY, стр. 529–561, MR 0175719.
- Кампеану, Цезарь; Кулик, Карел, II; Саломаа, Кай; Ю, Шэн (2001), "Сложность состояний основных операций на конечных языках", 4-й международный семинар по реализации автоматов (WIA '99) , конспект лекций по информатике, 2214 , Springer-Verlag, стр. 60–70, doi : 10.1007 / 3-540-45526-4_6 , ISBN 978-3-540-42812-1.
- Дэвид, Жюльен (2012), «Средняя сложность алгоритмов Мура и Хопкрофта», Теоретическая информатика , 417 : 50–65, DOI : 10.1016 / j.tcs.2011.10.011.
- Хопкрофт, Джон (1971), " Алгоритм n log n для минимизации состояний в конечном автомате", Теория машин и вычислений (Proc. Internat. Sympos., Технион, Хайфа, 1971) , Нью-Йорк: Academic Press, стр. 189–196, MR 0403320. См. Также предварительную версию Технического отчета STAN-CS-71-190 , Стэнфордский университет, факультет компьютерных наук, январь 1971 г.
- Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , чтение / MA: Addison-Wesley, ISBN 978-0-201-02988-8
- Хопкрофт, Джон Э .; Мотвани, Раджив ; Ульман, Джеффри Д. (2001), Введение в теорию автоматов, языки и вычисления (2-е изд.), Addison-Wesley.
- Камеда, Цунехико; Weiner, Питер (1970), "О государственной минимизации недетерминированных конечных автоматов", IEEE Transactions на компьютерах , 100 (7): 617-627, DOI : 10,1109 / TC.1970.222994 , S2CID 31188224.
- Knuutila, Тимо (2001), "Re-описания алгоритма с помощью Hopcroft", Теоретическая информатика , 250 (1-2): 333-363, DOI : 10.1016 / S0304-3975 (99) 00150-4 , МР 1795249.
- Leiss, Эрнст (1981), "Succinct представление регулярных языков с помощью булевых автоматов", Теоретическая информатика , 13 (3): 323-330, DOI : 10.1016 / S0304-3975 (81) 80005-9 , MR 0603263.
- Лейсс, Эрнст (1985), "Краткое представление регулярных языков логическими автоматами II", Теоретическая информатика , 38 : 133–136, DOI : 10.1016 / 0304-3975 (85) 90215-4
- Мур, Эдвард Ф. (1956), "Геданкен-эксперименты на последовательных машинах", Исследования автоматов , Анналы математических исследований, нет. 34, Princeton, NJ: Princeton University Press, pp. 129–153, MR 0078059.
- Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Cambridge University Press , ISBN 978-0-521-84425-3, Zbl 1188,68177
Внешние ссылки
- Минимизация DFA с использованием теоремы Майхилла-Нероде