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

#regex #finite-automata #regular-language

#регулярное выражение #конечные автоматы #обычный язык

Вопрос:

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

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

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

Ответ №1:

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

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

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

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

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

Комментарии:

1. хорошо, пока я доволен всем, вплоть до: ((a b) * Ub) . Как только я туда доберусь, я не знаю, что делать

2. Самая внешняя операция — * . Итак, сначала построил машину для (a b) U b. Самой внешней операцией здесь является U, поэтому создайте две машины: одну для (a b) и одну для b . Машина для b тривиальна. Для другого самая внешняя операция — * , поэтому создайте машину для b. Самой внешней операцией является конкатенация, поэтому создайте машины для a и b. Машина для b тривиальна. Самая внешняя операция для другого — * , поэтому создайте машину для a; это тривиально. Теперь вернитесь к стеку рекурсии и примените соответствующие правила для формирования замыканий, конкатенаций и объединений Kleene.

3. когда вы говорите, что это тривиально, вы имеете в виду, что мы перестаем строить на нем?

4. @tehman: вы читали доказательство теоремы Клини? Это дает алгоритм для преобразования конечных автоматов в регулярные выражения и наоборот. Если вы прочтете это, вы узнаете, что Patrick87 подразумевает под «тривиальным».

Ответ №2:

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