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

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

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

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

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

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

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


regular-language automaton computation-theory
person Blackgirl5    schedule 06.05.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Сначала это может показаться довольно сложным, но я предлагаю вам проверить определение 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 и a приводит к ba, но на этот раз выполняется объединение с предыдущим путем между q3 и q2;

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

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

person user2430343    schedule 10.05.2017