How to convert this DFA with multiple final states to a regular expression? (State elimination method)

Question

So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.

I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)a(ba) ... then q0 to f will be a(ba)*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?

Answer 1

When I eliminate say $q_1$, ..., now since $q_1$ has 2 outgoing transitions, '$a$' to $q_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q_1$, which are $q_0, q_2$ and $f$ when $q_1$ is eliminated.

• $\delta(q_0, ab)=q_0$
• $\delta(q_0, aa)=q_2$
• $\delta(q_0, a)=f$
• $\delta(q_2, a+bb)=q_0$
• $\delta(q_2, ba)=q_2$
• $\delta(q_2, \epsilon+b)=f$

$a(ba)^* + a(ba)^*a(ba)^*(aa(ba)^*a(ba)^*)^* + b(ab)^* + b(ab)^*b(ab)^*(bb(ab)^*b(ab)^*)*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$

Answer 2

My final answer was:

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

Just checking if it's right