# Converting DFA to RE with Arden's Rule

So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting correct regexes at least to my knowledge, I was having some weird issues with variables/state names. Please help me understand what my mistake is here in my process:

Consider the DFA that is governed by these equations and $$\Sigma = \{a, b\}$$: $$Q_0 = bQ_2 \cup aQ_1 \\ Q_1 = bQ_2 \cup aQ_0 \\ Q_2 = aQ_2 \cup bQ_2 \cup \varepsilon$$

I'm sorry I don't have a picture of the graph, but I think this should be fairly simple to visualize. It is an unminimized DFA that pretty much accepts every string with at least 1 'b', as it bounces back and forth from $$Q_1$$ and $$Q_0$$ every time an 'a' is reached, both $$Q_1$$ and $$Q_0$$ have edges to $$Q_2$$ from 'b', and $$Q_2$$ is an accept state that stays at $$Q_2$$ no matter what character it sees. Now I attempt to do the reduction method we see in Raphael's post:

$$Q_1 = bQ_2 \cup a(bQ_2 \cup aQ_1) \\ Q_1 = bQ_2 \cup abQ_2 \cup aaQ_1 \\ Q_1 = (b \cup ab)Q_2 \cup aaQ_1 \\ Q_1 = (aa)^*(b \cup ab)Q_2$$

$$\\ Q_2 = a^*bQ_2 \cup \varepsilon \\ Q_2 = a^*b^* \cup \varepsilon \\ Q_2 = (a^*b^*)^*$$

$$\\ \\ Q_1 = (aa)^*(b \cup ab)(a^*b^*)^*$$

Now I have two questions here:

1. Notice that at the end of my $$Q_1$$ manipulation I moved $$(aa)^*$$ to the front. This is something that I did out of common sense since thinking about the DFA, $$(aa)^*$$ has to be first since $$Q_2$$ doesn't have any outbound edges. Is there a way to formalize what I'm thinking/doing here?

2. Notice that at the end I have my valid regex equal to $$Q_1$$. That doesn't seem right, since we want to find the regex associated with $$Q_2$$! But a quick simulation through my head tells me that it actually is the regex associated with $$Q_2$$. So what is going on?!

Thanks so much for your help.

• In addition to D.W.'s comment below, I figured out that I was pretty much just skipping a step for my first question: it should be $Q_1 = (b \cup ab)Q_2 \cup aaQ_1 \Rightarrow Q_1 = aaQ_1 \cup (b \cup ab)Q_2 \Rightarrow Q_1 = (aa)^*(b \cup ab)Q_2$. This makes my application of Arden's Rule valid here. Dec 9, 2019 at 8:56

Your manipulation where you went from $$Q_1 = (b \cup ab)Q_2 \cup aaQ_1$$ to $$Q_1 = (aa)^*(b \cup ab)Q_2$$ was not valid. Instead, in this case I suggest that you first start by finding a nice form for $$Q_2$$, before trying to manipulate $$Q_1$$.

A good way to handle $$Q_2$$ is to note that $$Q_2 = a Q_2 \cup b Q_2 \cup \epsilon$$ implies $$Q_2 = (a \cup b) Q_2 \cup \epsilon$$ (by the distribute law); when then apply Arden's rule to conclude that $$Q_2 = (a \cup b)^* \epsilon = (a \cup b)^*$$.

Now plug in this expression for $$Q_2$$ into your equations for $$Q_0$$ and $$Q_2$$. You obtain

\begin{align*} Q_0 &= b (a \cup b)^* \cup a Q_1\\ Q_1 &= b (a \cup b)^* \cup a Q_0 \end{align*}

Next, take the expression for $$Q_1$$ and plug it into the first equation. We see that

$$Q_0 = b (a \cup b)^* \cup a b (a \cup b)^* \cup a a Q_0.$$

Now applying Arden's rule tells us that

$$Q_0 = (aa)^* (b \cup ab) (a \cup b)^*.$$

That's the regular expression that you ultimately wanted.

• Great, thank you for clearing my confusion about applying Arden's rule. A quick question though, in your solution, we have $Q_0$ = (the regex we want). However, in my hypothetical DFA, $Q_2$ is the accept state, so shouldn't we be getting a regex for $Q_2$? Or are we trying to find a regex for the start state of the machine? Thanks so much. Dec 9, 2019 at 8:46
• @CoolRobloxKid12, nope. The regexp that we get for $Q_0$ is the regexp that describes all strings that are accepted by the DFA, if you use $Q_0$ as the initial state of the DFA. That's what we want. The regexp we get for $Q_2$ describes all strings accepted by the DFA if you start at state $Q_2$ as your initial state. That's not what we want.
– D.W.
Dec 9, 2019 at 8:55
• Ok, thanks. I guess as a consequence to this then is that substituting for $Q_1$ producing the same regex is just a coincidence based on the way this DFA has been set up. Thank you so much for the help Dec 9, 2019 at 8:59