Минимизация DFA

Пример DFA. В состоянии c он демонстрирует то же поведение для каждой входной строки, что и в состоянии d или в состоянии e . Точно так же неотличимы состояния a и b . В DFA нет недоступных состояний.

Эквивалентный минимальный DFA. Неразличимые состояния объединены в одно.

В теории автоматов (раздел теоретической информатики ) минимизация DFA - это задача преобразования данного детерминированного конечного автомата (DFA) в эквивалентный DFA, который имеет минимальное количество состояний. Здесь два DFA называются эквивалентными, если они распознают один и тот же обычный язык . Известно несколько различных алгоритмов, решающих эту задачу, и они описаны в стандартных учебниках по теории автоматов. ^[1]

Минимальный DFA [ править ]

Для каждого регулярного языка также существует минимальный автомат, который его принимает, то есть DFA с минимальным количеством состояний, и этот DFA уникален (за исключением того, что состояниям можно давать разные имена). ^{[2] [3]} Минимальный DFA обеспечивает минимальные вычислительные затраты для таких задач, как сопоставление с образцом .

Есть два класса состояний, которые можно удалить или объединить из исходного DFA, не влияя на язык, который он принимает для его минимизации.

• Недостижимые состояния - это состояния, которые недоступны из начального состояния DFA для любой входной строки.
• Неразличимые состояния - это состояния , которые нельзя отличить друг от друга ни для одной входной строки.

Минимизация DFA обычно выполняется в три этапа, соответствующих удалению или слиянию соответствующих состояний. Поскольку устранение неотличимых состояний является наиболее затратным с точки зрения вычислений, обычно это делается в последнюю очередь.

Недостижимые состояния [ править ]

В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Сентябрь 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Состояние p детерминированного конечного автомата M = ( Q , Σ, δ, q ₀ , F ) недостижимо, если в Σ ^{* не} существует строки w, для которой p = δ ^* ( q ₀ , w ). В этом определении Q - это набор состояний, Σ - это набор входных символов, δ - это функция перехода (отображение состояния и входного символа в набор состояний), δ ^* - его расширение на строки, q ₀ - начальное состояние, а F- это набор принимающих (также называемых конечных) состояний. Достижимые состояния могут быть получены по следующему алгоритму:

пусть  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 ;

Недостижимые состояния можно удалить из DFA, не влияя на поддерживаемый язык.

Неразличимые состояния [ править ]

Алгоритм Хопкрофта [ править ]

Один из алгоритмов слияния неотличимых состояний DFA, предложенный Хопкрофтом (1971) , основан на уточнении разбиения, разбиении состояний DFA на группы по их поведению. Эти группы представляют собой классы эквивалентности на Myhill-Nerode отношением эквивалентности , причем каждые два состояния одного и того же раздела являются эквивалентными , если они имеют одинаковое поведение для всех входных последовательностей. То есть для каждых двух состояний p ₁ и p _2, которые принадлежат одному и тому же классу эквивалентности в разделе P , и для каждого входного слова w переходы, определяемые w, всегда должны принимать состоянияp ₁ и p ₂ в равные состояния, заявляет, что оба принимают, или заявляет, что оба отклоняют. Для w не должно быть возможностиперевести p ₁ в состояние приема, а p ₂ в состояние отклонения или наоборот.

Следующий псевдокод описывает алгоритм:

P  : =  { F ,  Q  \  F }; W  : =  { F ,  Q  \  F }; в то время как  ( W  это  не  пустые )  делать  выбор  и  удалить  в  набор  А  из  W  для  каждого  с  в  Е  делать  пусть  X  будет  набор из состояний для которых переход на гр приводит к             состояние  в  A  для  каждого  множества  Y  в  P  для  которого  X  ∩  Y  является  непустым  и  Y  \  Х  является  непустым  ли  заменить  Y  в  P с  помощью  тех  двух  множеств  X  ∩  Y  и  Y  \  X ,  если  Y  находится  в  W  заменить  Y  в  W  по  же два набора иначе, если |      X  ∩  Y |  <=  | Y  \  X |  добавить  X  ∩  Y  к  W  иначе  добавить  Y  \  X  к  W  end ;  конец ; конец ;

Алгоритм начинается с слишком грубого разбиения: каждая пара состояний, эквивалентных согласно соотношению Майхилла – Нероде, принадлежит одному и тому же набору в разбиении, но неэквивалентные пары также могут принадлежать одному и тому же набору. Он постепенно уточняет разбиение на большее количество меньших наборов, на каждом шаге разбивая наборы состояний на пары подмножеств, которые обязательно неэквивалентны. Начальное разделение - это разделение состояний на два подмножества состояний, которые явно не имеют такого же поведения, как друг друга: принимающие состояния и отклоняющие состояния. Затем алгоритм повторно выбирает набор 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 ² с ).: каждый шаг алгоритма может быть выполнен за время 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 для исходного языка.${\ displaystyle M}$${\ displaystyle M ^ {R}}$${\ displaystyle M_ {D} ^ {R}}$

Интуиция, лежащая в основе алгоритма, такова: после того, как мы определяем получение , мы меняем его, чтобы получить . Теперь имеет тот же язык, что и , но есть одно важное отличие: нет двух состояний, в которых мы могли бы принять одно и то же слово. Это следует из детерминированности, а именно. не существует двух состояний, в которые мы можем попасть из начального состояния с помощью одного и того же слова. Детерминизации затем создает powerstates (множество состояний ), где каждые два powerstates отличается - естественно - по крайней мере , одного состоянием в . Предположим и ; затем добавляет хотя бы одно слово ^{[примечание 2]}${\ displaystyle M ^ {R}}$${\ displaystyle M_ {D} ^ {R}}$${\ displaystyle M_ {D} ^ {R}}$${\ Displaystyle (M_ {D} ^ {R}) ^ {R} = M '}$${\ displaystyle M '}$${\ displaystyle M}$${\ displaystyle M '}$${\ displaystyle M_ {D} ^ {R}}$${\ displaystyle M_ {D} ^ {R}}$${\ displaystyle M '}$${\ displaystyle M '}$${\ displaystyle {\ mathcal {R}}, {\ mathcal {S}}}$${\ displaystyle q}$${\ displaystyle M '}$${\displaystyle q\in {\mathcal {R}}}$${\displaystyle q\not \in {\mathcal {P}}}$${\displaystyle q}$к языку ^{[примечания 3],} который не может присутствовать , поскольку это слово является уникальным (никакое другое государство его не принимает). Мы видим, что это справедливо для каждой пары состояний власти, и, таким образом, каждое состояние власти отличается от любого другого состояния власти. Следовательно, после определения у нас есть DFA без неразличимых или недостижимых состояний; следовательно, минимальный DFA для оригинала .${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle q}$${\displaystyle M'}$${\displaystyle {\overline {M}}}$${\displaystyle M}$

Если он уже детерминирован, то его достаточно обрезать, ^{[примечание 4]} перевернуть, детерминировать и затем снова отменить. Это можно рассматривать как начало в описанном выше процессе (при условии, что он уже был обрезан), поскольку входной FA уже детерминирован (но имейте в виду, что на самом деле это не реверсирование). Мы переворачиваем и детерминируем, чтобы получить , который является минимальным DFA для обращения языка (поскольку мы сделали только одно обращение). Теперь все, что осталось сделать, - это перевернуть, чтобы получить минимальный DFA для исходного языка.${\displaystyle M}$${\displaystyle M_{D}^{R}}$${\displaystyle M_{D}^{R}}$${\displaystyle {\overline {M}}}$${\displaystyle M}$${\displaystyle {\overline {M}}}$

Наихудшая сложность алгоритма Бжозовского экспоненциально зависит от числа состояний входного автомата. Это выполняется независимо от того, является ли вход NFA или DFA. В случае DFA экспоненциальный взрыв может произойти при детерминировании разворота входного автомата; ^{[примечание 5]} в случае NFA это также может произойти во время первоначального определения входного автомата. ^{[примечание 6]} Однако алгоритм часто работает лучше, чем можно было бы предположить в этом наихудшем случае. ^[6]

Минимизация NFA [ править ]

Хотя описанные выше процедуры работают для DFA, метод разделения не работает для недетерминированных конечных автоматов (NFA). ^[8] Хотя исчерпывающий поиск может минимизировать NFA, не существует алгоритма полиномиального времени для минимизации общих NFA, если только P = PSPACE , нерешенная гипотеза в теории вычислительной сложности, которая, как многие полагают, неверна. Однако есть методы минимизации NFA, которые могут быть более эффективными, чем перебор. ^[9]

См. Также [ править ]

• Кодирование состояния для низкого энергопотребления

Заметки [ править ]

Ссылки [ править ]

• Ахо, Альфред В .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (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.
• 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 с использованием теоремы Майхилла-Нероде