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:
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?
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.