0
$\begingroup$

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex?

  1. $1$
  2. $2$
  3. $4$
  4. $5$ or more

So for my understanding, this regex is equivalent to $(a^*b)^*$. I was able to build the following DFA, nevertheless, I know the answer is $2$. How is it possible?

enter image description here

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Your simplified regex is ok. Your automaton is not correct. You can have any number of consecutive $b$. BTW, you do not tell which is the initial state. And you do need 3 states if you have an explicit failure state. $\endgroup$
    – babou
    May 18 '15 at 17:49
  • 2
    $\begingroup$ Follow the algorithms you've seen in class; this is a rote exercise. (Note, though, that not all definitions of DFA require the existence of q_fail. Your material should be consistent about that. Hopefully.) $\endgroup$
    – Raphael ♦
    May 18 '15 at 18:10
  • $\begingroup$ @babou, so basically this regex can be translated to $L = \{a^nb^n : n \ge 0\}$. I still need the third state "q_fail" in order to handle the characters $c,d$, so I am still not sure how can it can be reduced to $2$ states.. $\endgroup$
    – Elimination
    May 18 '15 at 18:49
  • 1
    $\begingroup$ @Elimination The regexp certainly doesn't translate to $\{a^nb^n\mid n\geq 0\}$ because thats the canonical non-regular language. $\endgroup$
    – David Richerby
    May 18 '15 at 19:03
  • 1
    $\begingroup$ What the regex says is that you can have any string that is empty or ends with a $b$. But you need 2 states to distinguish whether you are allowed to accept, having just read a $b$ or not, plus a third state for failure when you read $c$ or $d$. But it is often the case that the failure state and corresponding transitions are left implicit. Try to understand why the regex reads as I said. $\endgroup$
    – babou
    May 18 '15 at 23:47
2
$\begingroup$

Your $\Sigma=\{a,b,c,d\}$ so you have to add at least one dead state. The DFA is: enter image description here

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Some authors have an implicit dead state by defining a DFA as one in which each state has at most one transition per symbol. Since 3 isn't an option, I guess whoever set the exercise in the quesion subscribes to that viewpoint. $\endgroup$
    – David Richerby
    May 18 '15 at 19:07
  • $\begingroup$ Interesting. However you can obtain the correct answer by discard. As we already generated a DFA with 3 states we can discard alternative 3 and 4. Alternative 1 is not possible because the DFA of one state denote a different language. So I would mark alternative 2 and ask an explanation from my teacher later haha. $\endgroup$
    – Renato Sanhueza
    May 18 '15 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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