Государственный Устранение DFA к регулярному выражению

Question

У меня есть несколько вопросов, касающихся устранения штата и терминологии.

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

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

, а нижний был бы

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

Было бы 0 (0 * (0 + 1)) 1 *?

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

Answer 1

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

после того, как значение RE исключения будет следующим:

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

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

Answer 2

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

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

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

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

В результате получится 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 получаем:

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

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