# DFA to regular expression conversion

I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.

The question, I was trying to solve is:

I have got the following equations:

$Q_0=aQ_0 \cup bQ_1 \cup \epsilon$

$Q_1=aQ_1 \cup bQ_1 \cup \epsilon$

When solved, we will get $Q_0=a^*b(a \cup b)^* \cup\ \epsilon$

But my doubt is that, in the DFA starting state is also the final state so, even if we dont give any $b$, it will be accepted, if we give some $a$. But in the regex we have $b$, instead of $b^*$. Why is it so? Is it because,we have that regex $\cup$ $\epsilon$ ?

• Your solution for the equations is wrong (well, clearly, because the regex is wrong. It doesn't accept e.g. $aa$, which it should). Can you detail how you solved the system? – Shaull Mar 1 '13 at 17:35
• On the first glance, I would say that your DFA accepts a very simple language, which you can easily express as a regular expression. – Dan Mar 1 '13 at 18:29

I'll be using the solution to $Q = \alpha Q \cup \beta$ given by $Q = \alpha^* \beta$, essentially as you would go solving a system of linear equations by hand:
\begin{align*} Q_0 &= a Q_0 \cup b Q_1 \cup \epsilon \\ Q_1 &= (a \cup b) Q_1 \cup \epsilon \end{align*} From the first equation you have $Q_0 = a^* (b Q_1 \cup \epsilon)$, the second one reduces to $Q_1 = (a \cup b)^* \epsilon = (a \cup b)^*$. Replacing $Q_1$ in $Q_0$ gives: $$Q_0 = a^* (b (a \cup b)^* \cup \epsilon) = a^* b (a \cup b)^* \cup a^*$$