# Convert DFA to Regular Expression

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?

:

:

• The book Introduction to Automata Theory, Languages, and Computation by Hopcroft, Ullman, Motwani describes this method of conversion of a DFA to a regular expression in detail. It is a very convenient method but requires some practice. – lgidwani Jul 21 '14 at 9:31
• Also, as an aside. The last image looks wrong and the final regular expression should be: bb + (a+ba)(ba)*(a+bb) since in the second image, q1 is looping on (ba) – Int_Casting Feb 19 '15 at 3:53

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.

The RE "aa" is not left out. First "a" in transaction between $q_0$ and $q_1$, second "a" between q1 and q3. Since this pair of transitions doesn't involve $q_2$ we don't consider it in the first stage of the algorithm, where we're eliminating $q_2$.

it is not left out , see q3 cn still be reachable using "aa" from intial state q1 , just tk 2nd term from unioned terms and then pick 'a' from (a+ba) , tk (ba)* as NULL String and then take 2nd 'a' from (a+bb) : so by concatenation we got "aa" and we reached final state q3

• What does this add over older answers? Also, I find your post hard to follow. – Raphael Jan 22 '17 at 18:57
• first of all u ve made a mistake in a question. you ve changed the order of a loop at state q1 , it is supposed to be (ba)* and not (ab)* , then i pointed out a simpler way to show you tht "aa" isnt left out , directly from the regular expression you got at the last – tolani Jan 24 '17 at 5:19