DFA to regular expression conversion

Problem Detail: 

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$ ?

Asked By : user5507

Answered By : vonbrand

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^* $$

Best Answer from StackOverflow

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