Преобразование состояния DFA в регулярное выражение

У меня есть несколько вопросов относительно исключения состояния и терминологии.

В приведенном выше примере показан DFA с принимающим состоянием, в котором вы должны начать с символа 0 и закончить с 1.

Если бы мне нужно было преобразовать его в регулярное выражение, верхнее значение было бы

а внизу будет

Вот моя проблема, я понятия не имею, как добавить верхнюю и нижнюю части в одно выражение. Я также не совсем уверен, как дальше исключить символ q2 1.

Будет ли это 0(0*(0+1))1* ?

Спасибо всем, кто может помочь!

Michael 04.12.2018 источник

comment

Исключение q2 приводит к (0+1+)+ для верхней диаграммы (я использую 0+ для демонстрации 00*. Знак плюс здесь не означает |). И второй будет 10*1+[10]* ([10] означает (0|1). Опять же, знак плюс здесь не обозначает |) - revo 04.12.2018

comment

Кроме того, регулярные выражения соответствуют только принимающему состоянию. Любое состояние отклонения не отражается в регулярных выражениях. Таким образом, вам вообще не нужно моделировать нижний регистр (начиная с 1), поскольку он никогда не должен приводить к состоянию принятия. - Corion 04.12.2018

Ответы (2)

arrow_upward
3
arrow_downward

Для выполнения этой задачи доступен гораздо более известный и понятный алгоритм.

Чтобы преобразовать DFA G в регулярное выражение, мы сначала преобразуем G в «GNFA». Пусть, например, G будет следующим DFA (q — начальное состояние):

Процесс преобразования DFA в GNFA выглядит следующим образом:

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

Это результирующий GNFA:

Затем мы удаляем каждое состояние между новым начальным состоянием и новым состоянием принятия по одному, корректируя график для поддержания правильности. Процесс работает следующим образом: пусть x, y и z будут состояниями в нашем DFA. Кроме того, переходы следующие: x->y на входе a, y->y на входе b и y->z на входе c. Скажем, мы хотим удалить y. Для каждого перехода из некоторой вершины n в y и для каждого перехода из y в m мы должны добавить новый переход n->m. Переход от n к m будет содержанием перехода от n к y, за которым следует содержание перехода y->y с клинской звездой, за которым следует содержание перехода от y->m. В этом случае x->y на a, y->y на b и y->z на c после удаления состояния y будет переход от x->z на a(b*)c.

Рассмотрим наш DFA на изображениях. После удаления состояния q получаем:

После удаления состояния r получаем:

Наконец, после удаления состояний у нас остается:

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

Philip DiSarro 09.12.2018

arrow_upward
0
arrow_downward

вы начинаете с состояния (q0), если вы вводите (0), то вы можете добраться до финала; вместо этого, если вы введете (1), вы не сможете достичь окончательного результата. поэтому рассмотрим только состояния (q0) (q1) (q2) и применим правило исключения к этим состояниям

после исключения RE будет следующим

0(0)*1 . (1+0(0)*1)*

начиная с 0 и заканчивая 1

sabeen kanwal 07.03.2019

Преобразование состояния DFA в регулярное выражение

Ответы (2)

Вопросы по теме