Построение регулярного выражения из конечных автоматов

Я пытаюсь создать регулярное выражение из конечного автомата, но обнаружил, что полностью застрял в этом. Регулярное выражение для использования выглядит следующим образом:

? = 0 или 1
* = 0 или больше
+= 1 или больше
| = or
_ = пустая строка
@ = пустой набор
() = круглые скобки

Насколько я понимаю, строки должны быть либо "b*", заканчивающимися на "a*", либо заканчиваться на "a+bb+"
Сейчас у меня есть ((b*(a+(bb))*)*), но это не учитывает строку, заканчивающуюся на "a" .

Как уже было сказано, я на 100% застрял в этом и просто не могу понять, как я должен работать с этим.

изображение: http://img593.imageshack.us/img593/2563/28438387.jpg

КОД:
Тип автомата
FA

Государства
q1
q2
q3
q4

Алфавит
а
б

Исходное состояние
q3

Конечные состояния
q3
q4

Переходы
q1 a q2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

Любые решения или советы приветствуются!


regex finite-automata automata
person mjuopperi    schedule 20.12.2010    source источник
comment
А как насчет b*(a+)?(bb+|bb+a+)??   -  person dheerosaur    schedule 20.12.2010
comment
Обвините меня в том, что я застрял в том, что никогда не думал об использовании (a+)?! Благодарю вас! Хотя я должен удостовериться, примет ли это babbabb или abbaabb? (т.е. делать более одного раунда)   -  person mjuopperi    schedule 20.12.2010
comment
извините, (a+)? формально эквивалентно a*   -  person Luis Colorado    schedule 27.04.2016

Ответы (2)


arrow_upward
0
arrow_downward

Невозможно перейти из q2 в конечное состояние. Удалите его, и полученный DFA будет легче конвертировать.

Насколько я понимаю, строки должны быть либо "b*", заканчиваться на "a*", либо заканчиваться на "a+bb+". Теперь у меня есть ((b*(a+(bb)))) но это не учитывает строку, оканчивающуюся на «а».

Представьте, что q3 не было конечным состоянием, а q4 было начальным состоянием. Как тогда будет выглядеть регулярное выражение? Изменить это на то, что вы хотите, не должно быть слишком сложно, просто не бойтесь иметь одно и то же состояние и/или переходы, описанные более чем одной частью регулярного выражения.

Еще один совет: я почти уверен, что вам нужно будет использовать либо ?, либо | хотя бы один раз.

person Laurence Gonsalves    schedule 20.12.2010
comment
Я в основном игнорировал q2 и просто считал, что за ab должна следовать хотя бы еще одна буква «b». (Таким образом, конец на a+bb+) - person mjuopperi; 20.12.2010
comment
@Gawwad Хорошо, я добавил еще несколько советов, основанных на конкретной проблеме, которую вы упомянули в своем вопросе. - person Laurence Gonsalves; 20.12.2010
comment
Будет ли это (a*(bb+a+)?)* ? Должен ли я использовать ()* по кругу для учета таких строк, как abbaabb, или это необходимо? - person mjuopperi; 20.12.2010
comment
@Gawwad Я думаю, что это ближе, хотя вы не сопоставляете одинокое b с этим регулярным выражением. Я не уверен, что вы подразумеваете под «раундом». Часто проще преобразовать регулярное выражение в FA, чем наоборот, поэтому вы можете попытаться преобразовать регулярное выражение в FA, а затем пройти через оба автомата вместе, чтобы увидеть, есть ли какие-либо пути к принимающему состоянию, которые существуют в одном, но не другой. - person Laurence Gonsalves; 20.12.2010
comment
Я немного неправильно выразился. Я имею в виду, будет ли a+b+ соответствовать abab или мне придется использовать ()* вокруг регулярного выражения, чтобы оно соответствовало рекурсивно? - person mjuopperi; 20.12.2010
comment
@Gawwad: Нет, a+b+ не соответствует abab. Он соответствует одной или нескольким буквам «а», за которыми следует одна или несколько букв «б». Да, (a+b+)* соответствует abab. - person Laurence Gonsalves; 20.12.2010
comment
@Gawwad: Извините, я только что понял, что в более раннем редактировании я не сказал того, что хотел сказать. Я хотел сказать, что Imagine q3 не был конечным состоянием. Игнорируйте и q4 был битом начального состояния. Это изменение должно упростить получение чего-то близкого к тому, что вы хотите. Хотя последнее регулярное выражение, которое у вас было в комментариях, тоже было недалеко от правильного... - person Laurence Gonsalves; 20.12.2010
comment
Если q3 не является окончательным, получится ли это (a+(bb+a+)?)* ? Я придумал ((b*(a+bb+)?)|(ba))* для исходной задачи. Но я думаю, что macthes ab. - person mjuopperi; 20.12.2010
comment
b*((a+bb+)|(a*))* Я думаю, должно быть правильным решением. Однако валидатор выдает мне эту ошибку. Учитывая, что регулярное выражение имеет другой алфавит, чем ожидалось. что не имеет для меня абсолютно никакого смысла. - person mjuopperi; 20.12.2010
comment
@Gawwad:"(a+(bb+a+)?)*" не совсем правильно. (например, это не соответствует аббабе). - person Laurence Gonsalves; 20.12.2010
comment
@Gawwad: Вот подход, который я бы использовал: грубо говоря, вам нужен + или * для каждого цикла. Есть 3 цикла: q4 для себя (a*) q3 для себя (b*) и цикл q4 для q1 для q3 до q4 (* для всего). Итак, у вас будет что-то вроде (...a*...b*)* в качестве основного цикла. Затем вам (возможно) потребуется добавить префикс, чтобы получить правильное начальное состояние, и, возможно, суффикс (ы) к конечному состоянию (ям). Также может помочь просто забыть о +, так как x+ — это просто сокращение от xx*. Вы всегда можете вернуться в конец и сжать использование * в +, где это уместно. - person Laurence Gonsalves; 20.12.2010
comment
@Gawwad: да, это кажется мне правильным решением. Существует несколько эквивалентных решений. Это долгий путь, но попробуйте превратить x+ в xx*. Некоторые механизмы регулярных выражений не поддерживают +. - person Laurence Gonsalves; 20.12.2010
comment
Миллион благодарностей, дружище, теперь понял! Последней ошибкой было то, что валидатор не принял «+». Счастливого Рождества! :) - person mjuopperi; 20.12.2010

arrow_upward
2
arrow_downward

Если вы передадите это инструментам для автоматов (например, Vcsn), вы взять это:

In [1]: import vcsn

In [2]: %%automaton a
   ...: $  -> q3
   ...: q1 -> q2 a
   ...: q1 -> q3 b
   ...: q2 -> q2 a
   ...: q2 -> q2 b
   ...: q3 -> q4 a
   ...: q3 -> q3 b
   ...: q4 -> q4 a
   ...: q4 -> q1 b
   ...: q3 -> $
   ...: q4 -> $
   ...: 
mutable_automaton<letterset<char_letters(ab)>, b>

In [3]: a.expression()
Out[3]: (b+aa*bb)*(\e+aa*)

где \e обозначает пустую строку. Тогда это только проблема преобразования синтаксиса.

Графически:

Графический рендеринг VCSN

См. этот пример в прямом эфире , и играйте с ним.

person akim    schedule 22.05.2015