Convert DFA to Regular Expression

Question Detail: 

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first. The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states $(q_0$,$q_1,q_3)$ such that:

1. We go from $q_0$ to $q_1$ with RE $a+ba$
2. We go from $q_0$ to $q_3$ with RE $bb$
3. We go from $q_1$ to $q_1$ with RE $ba$
4. We go from $q_1$ to $q_3$ with RE $a+bb$

I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

:

:

Asked By : user20232

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28517

Answered By : FrankW

The conversion in each step forms REs that describe

• The previous direct edge from one state to another and
• the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.