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

Question

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

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

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

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

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

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

States
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

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

Answer 1

Если вы передадите это инструментам для автоматов (например, 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 обозначает пустую строку.Тогда это только проблема преобразования синтаксиса.

Графически:

См. этот пример в реальном времени игрушка с ним.

Answer 2

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

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

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

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