#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 Вы всегда можете проверить, является ли ваше решение правильным или нет.