3
$\begingroup$

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:

enter image description here

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

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Mar 1, 2013 at 17:35
  • $\begingroup$ On the first glance, I would say that your DFA accepts a very simple language, which you can easily express as a regular expression. $\endgroup$
    – Dan
    Mar 1, 2013 at 18:29

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.