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