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
_ = 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!
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.
