Как преобразовать DFA в регулярное выражение?

Question

Я читаю книгу: введение в теорию вычислений и застрял на этом примере.

Преобразуйте DFA в эквивалентное выражение, преобразовав его сначала в GNFA(обобщенный недетерминированный конечный автомат), а затем преобразуйте GNFA в регулярное выражение.

вот пример: введите описание изображения здесь

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

К сожалению, я не могу понять, что происходит от b до c? Я только понимаю, что мы пытаемся избавиться от состояния 2, но как мы получаем C из b?

Большое спасибо!

Answer 1

Два популярных метода преобразования данного DFA в его регулярное выражение:

1. Метод Ардена
2. Метод исключения состояния

Теорема Ардена утверждает, что:

Пусть P и Q — два регулярных выражения над ∑.

Чтобы использовать теорему Ардена, должны быть выполнены следующие условия:

В диаграмме переходов не должно быть переходов ∈. Должно быть только одно начальное состояние.

Шаг-01:

Составьте уравнение для каждого состояния, учитывая переходы, которые приходят к этому состоянию. Добавьте '∈' в уравнение начального состояния.

Шаг-02:

Приведите конечное состояние к виду R = Q + RP, чтобы получить требуемое регулярное выражение.

Если P не содержит нулевой строки ∈, то

R = Q + RP имеет единственное решение, т.е. R = QP *

Answer 2

Поначалу это может быть довольно сложно, но я предлагаю вам проверить определение 1.64 и посмотреть функцию CONVERT(G) для большей ясности. Но в качестве краткого пояснения используем функцию для каждого возможного соседнего состояния:

• Сначала от a до b добавьте начальное состояние и новое принимаемое состояние;

• После этого вам нужно вычислить каждый новый путь после удаления qrip, в этом случае состояние 1;

• Таким образом, от начала до q2 вы получаете только метки a от epsilon и a;

• То же самое происходит от начала до q3, приводя только к b;

• Теперь от q2 до q2, проходящего через qrip, у вас есть метка a к qrip и метка a, чтобы вернуться, и вы получите (aa U b);

• То же самое относится к q3 - q3 через qrip, поэтому в результате bb обратите внимание, что в q3 нет цикла, поэтому нет объединения;

• Теперь от q2 до q3 через qrip вам нужно только объединить a и b, что приведет к метке ab;

• Наконец, наоборот, от q3 до q2, проходящего через qrip, конкатенация b и, в результате, ba, но на этот раз происходит объединение с предыдущим путем между q3 и q2;

• Теперь выберите новый qrip и продолжайте делать тот же алгоритм снова.

Надеюсь, что объяснение было достаточно ясным, но, как было сказано ранее, обратитесь к алгоритму в книге для лучшего и более подробного объяснения.