рисование минимального DFA для данного регулярного выражения

Регулярное выражение для DFA

Хотя НЕТ алгоритмического сокращения для рисования DFA из регулярного выражения (RE), но метод сокращения возможен путем анализа, а не путем вывода, он может сэкономить ваше время при рисовании минимизированного DFA. Но конечно технику можно освоить только на практике. Я беру ваш пример, чтобы показать мой подход:

(a + b)*ab   

Во-первых, подумайте о языке регулярного выражения. Если трудно определить, что такое описание языка с первой попытки, то найдите наименьшие возможные строки, которые можно сгенерировать на языке, а затем найдите второй наименьший.....

Запомните решение некоторых основных регулярных выражений. Например, я записал здесь некоторую основную идею написания леволинейного и прямолинейные грамматики непосредственно из регулярного выражения. Точно так же вы можете написать для построения минимизированного dfa.

В RE (a + b)*ab наименьшая возможная строка — ab, потому что с помощью (a + b)* можно сгенерировать NULL(^) строку. Вторая наименьшая строка может быть либо aab, либо bab. Теперь одна вещь, которую мы можем легко заметить о языке, заключается в том, что любая строка на языке этого RE всегда заканчивается на ab (суффикс), тогда как префиксом может быть любая возможная строка, состоящая из a и b, включая ^.

Также, если текущий символ a; тогда один из возможных шансов состоит в том, что следующим символом будет b и конец строки. Таким образом, в dfa нам требовался такой переход, чтобы всякий раз, когда символ b шел после символа a, он должен был перемещаться в одно из конечных состояний в dfa.

Затем, если новый символ приходит в конечное состояние, мы должны перейти в какое-то нефинальное состояние, потому что любой символ после b возможен только в середине некоторой строки на языке, так как вся языковая строка заканчивается суффиксом 'ab' .

Таким образом, с этими знаниями на данном этапе мы можем нарисовать неполную диаграмму перехода, как показано ниже:

--►(Q₀)---a---►(Q₁)---b----►((Q_{f< /под>))}

Теперь в этот момент вам нужно понять: каждое состояние имеет какое-то значение, например

(Q₀) означает = Начальное состояние
(Q₁) означает = Последний символ был «a», и с помощью еще одного «b» мы можем перейти к конечное состояние
(Q_f) означает = последние два символа были 'ab'

Теперь подумайте, что произойдет, если символ a перейдет в конечное состояние. Просто больше, чтобы указать Q₁, потому что это состояние означает, что последний символ был a. (обновленная диаграмма перехода)

--►(Q0)---a---►(Q1)---b----►((Qf))  
                ▲-----a--------|  

Но предположим, что вместо символа a в конечном состоянии появляется символ b. Затем мы должны перейти из конечного состояния в какое-то не конечное состояние. В данном графе переходов в этой ситуации мы должны сделать переход в начальное состояние из конечного состояния Q_f.(поскольку нам снова нужно ab в строке для принятия)

--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|  

Этот график все еще неполный! потому что нет исходящего ребра для символа a из Q₁. А для символа a в состоянии Q₁ требуется автоцикл, потому что Q₁ означает, что последний символ был a.

                a-  
                ||
                ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|     

Теперь я считаю, что все возможные исходящие ребра присутствуют из Q₁ и Q_f на приведенном выше графике. Одно недостающее ребро — это исходящее ребро из Q₀ для символа b. И должен быть цикл в состоянии Q₀, потому что снова нам нужна последовательность ab, чтобы строка могла быть принята. (смещение от Q₀ до Q_f возможно с помощью ab)

    b-          a-  
    ||          ||
    ▼|          ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|      

Теперь DFA готов!

Конечно, метод может показаться сложным при первых нескольких попытках. Но если вы научитесь рисовать таким образом, вы заметите улучшение своих аналитических способностей. И вы обнаружите, что этот метод является быстрым и объективным способом рисования DFA.

_{* В приведенной мной ссылке я описал еще несколько регулярных выражений, я настоятельно рекомендую вам изучить их и попытаться создать DFA для этих регулярных выражений.}