Search code examples
regexregular-languagefinite-automata

What is the regex equivalent of this finite automaton?

Finite automaton

I have never worked on fa to re conversions with two final states.

What should I do?

Should I just get rid of the other final state?

I got rid of q3 and I got 

(a*b(aa)*bb*ab)*

Or should I alternate and kleene star q1 to q3 and q1 to q3 to q1?

If I did that, I would get 

(a*b(aa)*bb* + a*b(aa)*bb*ab)*

which is kind of close since left-side of alternate can end in q3 and the other ends in q1. But then again, there's still the problem of that regex not accepting simple 'a' even if the fa clearly can.

Solution

  • To deal with multiple accepting states, split your DFA into multiple DFAs, each of which is identical to the original DFA, but which only has a single accepting state (one DFA for each accepting state in the original DFA). Now (independently) simplify each DFA (combine identical states and eliminate useless states) and create a regexp for each. The regexp for your original DFA will be the conjunction (combination with |) of all of these regexps.

    So in your case, you'll have two DFAs, one with only q0 as accepting and one with only q3. In the first of these, q1 and q3 are redundant(identical state transitions), so you can combine q3 into q1 (giving you a 3-state DFA where q1 loops on b). The regexp for that is:

    (a | b(b|aa)*b)*

    The regexp for the DFA with only q3 is much trickier. First find the paths to q3:

    a*b(aa|aba*b)*b

    then append the loops from q3:

    (b | a(a|ba*b)(a(a|ba*b))*b)*

    putting all that together:

    (a|b(b|aa)*b)* | a*b(aa|aba*b)*b(b|a(a|ba*b)(a(a|ba*b))*b)*

    not a simple regexp