Constructing a Regular Expression from a Finite Automata

I'm trying to construct a regular expression from a Finite Automaton but found my self completely stuck with this one. The regex to use is like this:

? = 0 or 1

* = 0 or more

+= 1 or more

| = or

_ = 开发者_JS百科empty string

@ = empty set

() = parentheses

As I understand the strings must either be "b*" end with "a*" or end with "a+bb+"

What i have now is ((b*(a+(bb))*)*) but that doesn't take into account a string ending with 'a'.

As said, I'm 100% stuck with this and just can't get my head around how I am supposed to work with this.

image: http://img593.imageshack.us/img593/2563/28438387.jpg

CODE:

Type of the automaton

FA

States

q1

q2

q3

q4

Alphabet

a

b

Initial state

q3

Final states

q3

q4

Transitions

q1 a q2

q1 b q3

q2 a q2

q2 b q2

q3 a q4

q3 b q3

q4 a q4

q4 b q1

Any solutions or tips appreciated!

If you feed this to tools for automata (e.g., Vcsn), you'd get this:

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*)

where \e denotes the empty string. Then it's only a problem of syntax conversion.

Graphically:

See this example live, and toy with it.

It isn't possible to get from q2 to a final state. Remove it and the resulting DFA should be easier to convert.

As I understand the strings must either be "b*" end with "a*" or end with "a+bb+" What i have now is ((b*(a+(bb)))) but that doesn't take into account a string ending with 'a'.

Imagine q3 was not a final state, and q4 was the initial state. What would the regex look like then? Changing that into what you want shouldn't be too hard, just don't be afraid to have the same state and/or transitions described by more than one part of the regex.

One more hint: I'm pretty sure you're going to need to use either ? or | at least once.