# What is the minimal number of states for the DFA?

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?

• 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. May 18, 2015 at 17:49
• 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.)
– Raphael
May 18, 2015 at 18:10
• @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.. May 18, 2015 at 18:49
• @Elimination The regexp certainly doesn't translate to $\{a^nb^n\mid n\geq 0\}$ because thats the canonical non-regular language. May 18, 2015 at 19:03
• 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. May 18, 2015 at 23:47

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