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

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

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

В теории автоматов (раздел теоретической информатики ) минимизация ДКА — это задача преобразования данного детерминированного конечного автомата (ДКА) в эквивалентный ДКА, имеющий минимальное количество состояний. Здесь два ДКА называются эквивалентными, если они распознают один и тот же регулярный язык . Несколько различных алгоритмов, решающих эту задачу, известны и описаны в стандартных учебниках по теории автоматов.

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

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

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

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

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

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

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

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

let reachable_states := {q0}
let new_states := {q0}

do {
    temp := the empty set
    for each q in new_states do
        for each c in Σ do
            temp := temp ∪ {p such that p = δ(q,c)}
    new_states := temp \ reachable_states
    reachable_states := reachable_states ∪ new_states
} while (new_states ≠ the empty set)

unreachable_states := Q \ reachable_states

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

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

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

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

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

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

Следующий псевдокод описывает форму алгоритма, заданную Сюй. Также были представлены альтернативные формы.

P := {F, Q \ F}
W := {F, Q \ F}

while (W is not empty) do
    choose and remove a set A from W
    for each c in Σ do
        let X be the set of states for which a transition on c leads to a state in A
        for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
            replace Y in P by the two sets X ∩ Y and Y \ X
            if Y is in W
                replace Y in W by the same two sets
            else
                if |X ∩ Y| <= |Y \ X|
                    add X ∩ Y to W
                else
                    add Y \ X to W

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

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

что у нас есть класс эквивалентности 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 ) шагов разделения в алгоритме. Структура данных уточнения раздела позволяет выполнять каждый шаг разделения за время, пропорциональное количеству переходов, которые в нем участвуют. Это остается наиболее эффективным алгоритмом, известным для решения проблемы, и для некоторых распределений входных данных его сложность в среднем еще выше, O ( n log log n ) .

После того, как алгоритм Хопкрофта был использован для группировки состояний входного 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 ) в зависимости от случайного распределения на автоматах, выбранных для смоделируйте поведение алгоритма в среднем случае.

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

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

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

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

После того, как мы определим $M^{R}$ чтобы получить $M_{D}^{R}$, мы отменяем это $M_{D}^{R}$ чтобы получить $(M_{D}^{R})^{R}=M'$. Сейчас $M'$ распознает тот же язык, что и $M$, но есть одно важное отличие: в $M'$ из которого мы можем принять одно и то же слово. Это следует из $M_{D}^{R}$ быть детерминистическим, т.е. в стране нет двух государств $M_{D}^{R}$ которого мы можем достичь из исходного состояния посредством одного и того же слова. Определение $M'$ затем создает powerstates (наборы состояний $M'$), где каждые два состояния власти ${\mathcal {R}},{\mathcal {S}}$ различаются ‒ естественно ‒ хотя бы в одном состоянии $q$ из $M'$. Предполагать $q\in {\mathcal {R}}$ и $q\not \in {\mathcal {S}}$; затем $q$ вносит хотя бы одно слово на язык ${\mathcal {R}}$, которого не может быть в ${\mathcal {S}}$, поскольку это слово уникально для $q$ (ни одно другое государство это не принимает). Мы видим, что это справедливо для каждой пары мощных состояний, и, таким образом, каждое энергетическое состояние отличается от любого другого энергетического состояния. Поэтому после определения $M'$, у нас есть DFA без неразличимых или недостижимых состояний; следовательно, минимальный ДКА ${\overline {M}}$ для оригинала $M$.

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

Сложность

В худшем случае сложность алгоритма Бжозовского экспоненциально зависит от числа состояний входного автомата. Это справедливо независимо от того, являются ли входные данные NFA или DFA. В случае DFA экспоненциальный взрыв может произойти во время определения обращения входного автомата; в случае NFA это может произойти и при первоначальном определении входного автомата. Однако алгоритм часто работает лучше, чем можно было бы предположить в этом худшем случае.

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

Основная статья: Минимизация NFA

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

См. также

• Кодирование состояния для малой мощности

Ссылки

• Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974), «4.13 Разделение», Проектирование и анализ компьютерных алгоритмов , Аддисон-Уэсли, стр. 157–162 .
• Берстель, Жан; Боассон, Люк; Картон, Оливье; Фагно, Изабель (2010), «Минимизация автоматов», Автоматы: от математики к приложениям , Европейское математическое общество , arXiv : 1010.5318 , Bibcode : 2010arXiv1010.5318B
• Бжозовский, Дж. А. (1963), "Канонические регулярные выражения и минимальные графы состояний для определенных событий", Proc. Симпозиумы. Математика. Теория автоматов (Нью-Йорк, 1962) , Политехническое издательство Политехнического института. Бруклина, Бруклин, Нью-Йорк, стр. 529–561, MR   0175719 .
• Кампеану, Цезарь; Чулик, Карел II; Саломаа, Кай; Ю, Шэн (2001), «Состояние сложности основных операций на конечных языках», Реализация автоматов , Конспекты лекций по информатике, том. 2214, Springer-Verlag, стр. 60–70, номер документа : 10.1007/3-540-45526-4_6 , ISBN.  978-3-540-42812-1 .
• Дэвид, Жюльен (2012), «Средняя сложность алгоритмов Мура и Хопкрофта», Theoretical Computer Science , 417 : 50–65, doi : 10.1016/j.tcs.2011.10.011 .
• Хопкрофт, Джон (1971), « Алгоритм n log n для минимизации состояний в конечном автомате», Теория машин и вычислений (Proc. Internat. Sympos., Технион, Хайфа, 1971) , Нью-Йорк: Academic Press, стр. 189–196, МР   0403320 . См. также предварительную версию, Технический отчет STAN-CS-71-190 , Стэнфордский университет, факультет компьютерных наук, январь 1971 г.
• Хопкрофт, Джон Э.; Уллман, Джеффри Д. (1979), Введение в теорию автоматов, языки и вычисления , Ридинг/Магистратура: Аддисон-Уэсли, ISBN  978-0-201-02988-8
• Хопкрофт, Джон Э .; Мотвани, Раджив ; Уллман, Джеффри Д. (2001), Введение в теорию автоматов, языки и вычисления (2-е изд.), Аддисон-Уэсли .
• Камеда, Цунехико; Вайнер, Питер (1970), «О минимизации состояния недетерминированных конечных автоматов», IEEE Transactions on Computers , 100 (7): 617–627, doi : 10.1109/TC.1970.222994 , S2CID   31188224 .
• Кнуутила, Тимо (2001), «Переописание алгоритма Хопкрофта», Theoretical Computer Science , 250 (1–2): 333–363, doi : 10.1016/S0304-3975(99)00150-4 , MR   1795249 .
• Лейсс, Эрнст (1981), «Краткое представление регулярных языков с помощью булевых автоматов», Theoretical Computer Science , 13 (3): 323–330, doi : 10.1016/S0304-3975(81)80005-9 , MR   0603263 .
• Лейсс, Эрнст (1985), «Краткое представление регулярных языков булевыми автоматами II», Theoretical Computer Science , 38 : 133–136, doi : 10.1016/0304-3975(85)90215-4
• Мур, Эдвард Ф. (1956), «Геданкен-эксперименты на последовательных машинах», Исследования автоматов , Анналы математических исследований, вып. 34, Принстон, Нью-Джерси: Издательство Принстонского университета, стр. 129–153, MR   0078059 .
• Сакарович, Жак (2009), Элементы теории автоматов , перевод с французского Рубена Томаса, Cambridge University Press , ISBN  978-0-521-84425-3 , Збл   1188,68177

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

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