Я нашел диаграмму состояний DFA (детерминированный конечный автомат) с его RegEx в скрипте, но эта диаграмма является просто образцом без каких-либо пояснений. Поэтому я попытался самостоятельно вывести RegEx из диаграммы состояний DFA и получил выражение: ab+a+b(a*b)*. Я не понимаю, как я получаю оригинальное RegEx (ab+a*)+ab+, упомянутое в сценарии. Вот мой вывод:
Буду благодарен за любую помощь, ссылки, ссылки и подсказки!
Вы правильно получили регулярное выражение здесь. Выражение, которое у вас есть 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, которое принимает и где мы можем взять цикл self и прочитать столько b, сколько захотим.
В противном случае у нас есть 1 или более копий (ab+a*), снова читая a из второй половины перехода a*a от 2 к 3 и b из перехода 3 к 4. a* происходит из первой половины цикла a*ab в состоянии 4, а вторая половина ab является либо последним ab+ регулярного выражения, либо началом другой копии (ab+a*). Я не уверен, есть ли исключение состояния, которое приводит именно к выражению (ab+a*)+ab+, но что бы это ни стоило, я думаю, что полученное вами регулярное выражение более четко отражает структуру этого DFA.
(ab+a*)+ab+изab+a+b(a*b)*? - person PatrickSteiner schedule 18.12.2017