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

Задача преобразования детерминированного конечного автомата

Пример DFA. Если в состоянии , он демонстрирует то же поведение для каждой входной строки, что и в состоянии , или в состоянии . Аналогично состояния и неразличимы. DFA не имеет недостижимых состояний. ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle b}$

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

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

Минимальный DFA

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

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

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

Минимизация DFA обычно выполняется в три этапа:

1. удалить мертвые и недостижимые состояния (это ускорит следующий шаг),
2. объединить неразличимые состояния,
3. при желании можно заново создать одно мертвое состояние (состояние «слива»), если требуется, чтобы полученный DFA был полным.

Недостижимые состояния

Состояние детерминированного конечного автомата недостижимо, если не существует строки в , для которой . В этом определении — набор состояний, — набор входных символов, — функция перехода (отображающая состояние и входной символ в набор состояний), — ее расширение для строк (также известное как расширенная функция перехода), — начальное состояние, — набор принимающих (также известных как конечные) состояний. Достижимые состояния можно получить с помощью следующего алгоритма: ${\displaystyle p}$ ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$ ${\displaystyle w}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle p=\delta ^{*}(q_{0},w)}$ ${\displaystyle Q}$ ${\displaystyle \Sigma }$ ${\displaystyle \delta }$ ${\displaystyle \delta ^{*}}$ ${\displaystyle q_{0}}$ ${\displaystyle F}$

пусть  достижимые_состояния  :=  { q0 } пусть  новые_состояния  :=  { q0 }do  {  temp  :=  пустое  множество  для каждого q в new_states do для каждого c в Σ do temp := temp ∪ { δ ( q , c )} new_states : = temp \ reachable_states reachable_states : = reachable_states ∪ new_states } while (  new_states ≠ пустое множество )                                недостижимые_состояния  :=  Q  \  достижимые_состояния

Предполагая эффективную реализацию множеств состояний (например, new_states) и операций над ними (таких как добавление состояния или проверка его наличия), этот алгоритм может быть реализован со сложностью по времени , где — число состояний, а — число переходов входного автомата. ${\displaystyle O(n+m)}$ ${\displaystyle n}$ ${\displaystyle m}$

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

Неразличимые состояния

Следующие алгоритмы представляют различные подходы к объединению неразличимых состояний.

Алгоритм Хопкрофта

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

Следующий псевдокод описывает форму алгоритма, заданную Сюй. ^[4] Также были представлены альтернативные формы. ^{[5] [6]}

П  :=  { Ж ,  Q  \  Ж } В  :=  { Ж ,  Q  \  Ж }while  ( W  не  пусто  ) do выбрать и удалить множество A из W для каждого c в Σ do пусть X будет множеством состояний , для которых переход по c приводит к состоянию в A для каждого множества Y в P , для которого X ∩ Y непусто и Y \ X непусто do заменить Y в P двумя множествами X ∩ Y и Y \ X , если Y находится в W replace Y в W теми же двумя множествами else if | X ∩ Y | < = | Y \ X | добавить X ∩ Y к W else добавить Y \ X к W​​​​​​​                                                                                                         

Алгоритм начинается со слишком грубого разбиения: каждая пара состояний, эквивалентных согласно сравнению Нерода, принадлежит одному и тому же набору в разбиении, но пары, которые неэквивалентны, также могут принадлежать одному и тому же набору. Он постепенно уточняет разбиение на большее количество меньших наборов, на каждом шаге разбивая наборы состояний на пары подмножеств, которые обязательно неэквивалентны. Начальное разбиение представляет собой разделение состояний на два подмножества состояний, которые явно не имеют одинакового поведения друг с другом: принимающие состояния и отвергающие состояния. Затем алгоритм многократно выбирает набор A из текущего разбиения и входной символ c и разбивает каждый из наборов разбиения на два (возможно, пустых) подмножества: подмножество состояний, которые приводят к A на входном символе c , и подмножество состояний, которые не приводят к A. Поскольку уже известно, что A имеет другое поведение, чем другие наборы разбиения, подмножества, которые приводят к A, также имеют другое поведение, чем подмножества, которые не приводят к A. Если больше не удается найти разбиений этого типа, алгоритм завершает работу.

Лемма . При наличии фиксированного символа c и класса эквивалентности Y , который распадается на классы эквивалентности B и C , для уточнения всего разбиения необходим только один из B или C. ^[7]

Пример: Предположим, что у нас есть класс эквивалентности 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оператора ( if Y is in W) является исправление W , набора отличительных признаков. Мы видим в предыдущем операторе в алгоритме, что Y только что был разделен. Если Y находится в W , он просто устарел как средство разделения классов в будущих итерациях. Поэтому Y должен быть заменен обоими разделениями из-за наблюдения выше. Однако, если Y не находится в W , только одно из двух разделений, а не оба, необходимо добавить к W из-за леммы выше. Выбор меньшего из двух разделений гарантирует, что новое дополнение к W будет не более половины размера Y ; это ядро ​​алгоритма Хопкрофта: как он получает свою скорость, как объясняется в следующем абзаце.

Худшее время выполнения этого алгоритма составляет O ( ns log n ) , где n — число состояний, а s — размер алфавита. Эта граница следует из того факта, что для каждого из ns переходов автомата множества, взятые из Q , которые содержат целевое состояние перехода, имеют размеры, которые уменьшаются относительно друг друга в два или более раз, поэтому каждый переход участвует в O (log n ) шагах разделения в алгоритме. Структура данных уточнения разделов позволяет выполнять каждый шаг разделения за время, пропорциональное числу переходов, которые в нем участвуют. ^[8] Это остается самым эффективным алгоритмом, известным для решения задачи, и для определенных распределений входных данных его средняя сложность даже лучше, O ( n log log n ) . ^[6]

После того, как алгоритм Хопкрофта был использован для группировки состояний входного DFA в классы эквивалентности, минимальный DFA может быть построен путем формирования одного состояния для каждого класса эквивалентности. Если S — это набор состояний в P , s — это состояние в S , а c — это входной символ, то переход в минимальном DFA из состояния для S на входе c переходит в набор, содержащий состояние, в которое входной автомат перешел бы из состояния s на входе c . Начальное состояние минимального DFA — это то, которое содержит начальное состояние входного DFA, а принимающие состояния минимального DFA — это те, члены которых являются принимающими состояниями входного DFA.

Алгоритм Мура

Алгоритм Мура для минимизации DFA принадлежит Эдварду Ф. Муру  (1956). Как и алгоритм Хопкрофта, он поддерживает разделение, которое начинается с разделения принимающих и отклоняющих состояний, и многократно уточняет разделение до тех пор, пока больше уточнений быть не может. На каждом шаге он заменяет текущее разделение самым грубым общим уточнением s + 1 разделов, один из которых является текущим, а остальные являются прообразами текущего раздела под функциями перехода для каждого из входных символов. Алгоритм завершается, когда эта замена не меняет текущий раздел. Его наихудшая временная сложность составляет O ( n ² s ) : каждый шаг алгоритма может быть выполнен за время O ( ns ) с использованием варианта радиксной сортировки для переупорядочивания состояний так, чтобы состояния в одном и том же наборе нового раздела были последовательными в порядке, и существует не более n шагов, поскольку каждый, кроме последнего, увеличивает количество наборов в разделе. Примеры задачи минимизации DFA, которые вызывают наихудшее поведение, такие же, как и для алгоритма Хопкрофта. Количество шагов, которые выполняет алгоритм, может быть намного меньше n , поэтому в среднем (для постоянного s ) его производительность составляет O ( n log n ) или даже O ( n log log n ) в зависимости от случайного распределения на автоматах, выбранных для моделирования поведения алгоритма в среднем случае. ^{[6] [9]}

Алгоритм Бжозовского

Обратные переходы недетерминированного конечного автомата (NFA) и переключение начальных и конечных состояний ^{[примечание 1]} создают NFA для обращения исходного языка. Преобразование этого NFA в DFA с использованием стандартной конструкции powerset (сохраняя только достижимые состояния преобразованного DFA) приводит к DFA для того же обращенного языка. Как заметил Brzozowski (1963), повторение этого обращения и определения во второй раз, снова сохраняя только достижимые состояния, создает минимальный DFA для исходного языка. ${\displaystyle M}$ ${\displaystyle M^{R}}$ ${\displaystyle M_{D}^{R}}$

Интуиция, лежащая в основе алгоритма, такова: определение обратного автомата объединяет состояния, которые неразличимы в исходном автомате, но могут производить несколько принимающих состояний. В таком случае, когда мы обращаем автомат во второй раз, эти принимающие состояния становятся начальными, и, таким образом, автомат не будет детерминированным из-за наличия нескольких начальных состояний. Вот почему нам нужно определить его снова, получив минимальный DFA.

Доказательство правильности

После того, как мы определили , чтобы получить , мы обращаем это , чтобы получить . Теперь распознает тот же язык, что и , но есть одно важное отличие: нет двух состояний в , из которых мы можем принять одно и то же слово. Это следует из детерминированности, а именно, нет двух состояний в , в которые мы можем прийти из начального состояния через одно и то же слово. Детерминизация затем создает состояния мощности (наборы состояний ), где каждые два состояния мощности отличаются ‒ естественно ‒ по крайней мере одним состоянием . Предположим и ; затем вносит по крайней мере одно слово ^{[примечание 2]} в язык , ^{[примечание 3]} которое не может присутствовать в , поскольку это слово уникально для (никакое другое состояние его не принимает). Мы видим, что это справедливо для каждой пары состояний мощности, и, таким образом, каждое состояние мощности отличимо от любого другого состояния мощности. Следовательно, после определения у нас есть DFA без неразличимых или недостижимых состояний; следовательно, минимальный DFA для исходного . ${\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 {S}}}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle q}$ ${\displaystyle M'}$ ${\displaystyle {\overline {M}}}$ ${\displaystyle M}$

Сложность

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

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

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

Смотрите также

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

Примечания

1. Хопкрофт, Мотвани и Ульман (2001), Раздел 4.4.3, «Минимизация DFA».
2. Хопкрофт и Ульман (1979), Раздел 3.4, Теорема 3.10, стр.67
3. Хопкрофт, Мотвани и Ульман (2001), Раздел 4.4.3, «Минимизация DFA», стр. 159 и стр. 164 (замечание после теоремы 4.26)
4. Сюй, Инцзе (2009). «Описание алгоритма n log n для минимизации состояний в детерминированном конечном автомате». стр. 5. S2CID  14461400. {{cite web}}: Отсутствует или пусто |url=( помощь )
5. Кнуутила (2001)
6. Берстель и др. (2010).
7. На основе следствия 10 Кнуутилы (2001).
8. Хопкрофт (1971); Ахо, Хопкрофт и Ульман (1974)
9. Дэвид (2012).
10. Хопкрофт, Мотвани и Ульман (2001), Раздел 4.4, Рисунок с надписью «Минимизация состояний НКА», стр. 163.
11. Камеда и Вайнер (1970).

1. M имеется несколько конечных состояний , мы должны либо разрешить несколько начальных состояний при обращении M , либо добавить дополнительное состояние с ε-переходами ко всем начальным состояниям и сделать только это новое состояние начальным.
2. M ' нет мертвых состояний ; таким образом, из каждого состояния принимается по крайней мере одно слово.
3. Язык штата — это набор слов, принятых в этом штате.
4. Например, язык двоичных строк, n- й символ которого является единицей, требует только n + 1 состояний, но его обращение требует 2 ⁿ состояний. Leiss (1981) предоставляет тернарный n -состоянный DFA, обращение которого требует 2 ⁿ состояний, максимально возможного. Для дополнительных примеров и наблюдения связи между этими примерами и анализом наихудшего случая алгоритма Brzozowski см. Câmpeanu et al. (2001).
5. Экспоненциальный взрыв произойдет максимум один раз, а не в обоих определениях. То есть алгоритм в худшем случае экспоненциальный, а не дважды экспоненциальный.

Ссылки

• Ахо, Альфред В.; Хопкрофт , Джон Э .; Ульман, Джеффри Д. (1974), «4.13 Разбиение», Проектирование и анализ компьютерных алгоритмов , Addison-Wesley, стр. 157–162.
• Берстель, Жан; Боассон, Люк; Картон, Оливье; Фаньот, Изабель (2010), «Минимизация автоматов», Автоматы: от математики к приложениям , Европейское математическое общество , arXiv : 1010.5318 , Bibcode : 2010arXiv1010.5318B
• Brzozowski, JA (1963), "Канонические регулярные выражения и минимальные графы состояний для определенных событий", Proc. Sympos. Math. Theory of Automata (Нью-Йорк, 1962) , Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, NY, стр. 529–561, MR  0175719.
• Câmpeanu, Cezar; Culik, Karel II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", Реализация автоматов , Lecture Notes in Computer Science, т. 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 для минимизации состояний в конечном автомате», Теория машин и вычислений (Труды Международного симпозиума, Технион, Хайфа, 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.
• Камеда, Цунехико; Вайнер, Питер (1970), «О минимизации состояний недетерминированных конечных автоматов», IEEE Transactions on Computers , 100 (7): 617–627, doi :10.1109/TC.1970.222994, S2CID  31188224.
• Кнутила, Тимо (2001), «Повторное описание алгоритма Хопкрофта», Теоретическая информатика , 250 (1–2): 333–363, doi :10.1016/S0304-3975(99)00150-4, MR  1795249.
• Лейсс, Эрнст (1981), «Краткое представление регулярных языков булевыми автоматами», Теоретическая информатика , 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 University Press, стр. 129–153, MR  0078059.
• Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Cambridge University Press , ISBN 978-0-521-84425-3, Збл  1188.68177

Внешние ссылки

• Минимизация DFA с использованием теоремы Майхилла–Нерода