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

Question

Как бы я изменил следующее регулярное выражение на конечные автоматы?

(abUb)(bUaaa)b*b((a*b)*Ub)*

примечание: в данном случае U означает объединение

Answer 1

Существует пять составных компонентов верхнего уровня этого регулярного выражения. Согласно алгоритму, восстанавливаемому из части теоремы Клини, вы можете сделать NFA-лямбды для них, а затем сформировать конкатенацию, соединив конечные состояния одного с начальными состояниями следующего.

Когда вы видите объединение, это означает, что вы делаете две машины и объединяете их, создавая новое начальное состояние с двумя лямбда-переходами.

Закрытие Клини немного сложнее, но в основном делает машину для повторяющейся вещи, затем преобразует ее, добавляя новое принимающее начальное состояние и цикл к нему из старых конечных состояний.

Базовый регистр - это машина для одной буквы, которая состоит из двух состояний, начального и конечного, с соответствующим помеченным переходом.

Работайте рекурсивно от самых простых машин (самые внутренние подвыражения) до целого, комбинируя при необходимости. Упростите результат настолько, насколько вам нравится, возможно, преобразовав его в минимальный DFA.

Answer 2

Существует приложение под названием Автоматический генератор кода Java для регулярных выражений и конечных автоматов, которое автоматически генерирует NFA, DFA (включая таблицу переходов) и Java-код для заданного регулярного выражения или конечных автоматов. Его можно скачать по этой ссылке: www.s-solutions.info Вы всегда можете проверить правильность вашего решения.