Как вывести RegEx из диаграммы состояния?

Question

Я нашел диаграмму состояний DFA (детерминированного конечного автомата) с его RegEx в скрипте, но эта диаграмма - просто образец без каких-либо объяснений. Поэтому я попытался вывести RegEx из диаграммы состояний DFA самостоятельно и получил выражение: ab+a+b(a*b)*, Я не понимаю, как я получаю оригинальный RegEx (ab+a*)+ab+ упоминается в сценарии. Вот мой вывод:

Я благодарен за любую помощь, ссылки, ссылки и советы!

Answer 1

Вы правильно вывели регулярное выражение. Выражение у вас есть ab+a+b(a*b)* эквивалентно (ab+a*)+ab+ - после того как вы завершили исключение состояния DFA (у вас есть один переход из начального состояния в принимающее состояние), больше не нужно делать деривации. Однако вы можете получить различные конечные регулярные выражения в зависимости от порядка, в котором вы удаляете состояния, и все они должны быть действительными, если вы правильно выполнили исключения. Также не гарантируется, что метод исключения состояний будет способен генерировать все эквивалентные регулярные выражения для определенного DFA, так что все в порядке, что вы не пришли точно к исходному регулярному выражению. Вы также можете проверить эквивалентность двух регулярных выражений здесь.

Для вашего конкретного примера, хотя бы показать, что этот DFA эквивалентен этому оригинальному регулярному выражению (ab+a*)+ab+посмотрите на DFA в этом состоянии исключения (где-то между вторым и третьим шагами, которые вы показали выше):

Давайте расширим наше выражение (ab+a*)+ab+ в (ab+a*)(ab+a*)*ab+, Так что в DFA первый (ab+a*) переводит нас из состояния 0 в состояние между состояниями 2 и 3 (a* в a*a).

Тогда следующая часть (ab+a*)* означает, что нам разрешено иметь 0 или более копий (ab+a*), Если есть 0 копий, мы просто закончим с ab+, читая a со второй половины a*a переход с 2 на 3 а b от перехода 3 к 4, посадка нас в состояние 4, которое принимает и где мы можем взять цикл самообучения и прочитать как можно больше bэто как мы хотим.

В противном случае у нас есть 1 или более копий (ab+a*)опять читаю a со второй половины a*a переход с 2 на 3 а b от 3 до 4 перехода. a* происходит из первой половины a*ab Сам цикл на состояние 4 и вторая половина ab либо финал ab+ регулярного выражения или начало другой копии (ab+a*), Я не уверен, есть ли устранение состояния, которое приходит именно к выражению (ab+a*)+ab+ но я думаю, что полученное вами выражение более четко отражает структуру этого DFA.