Minimum number of states of a DFA recognizing the regular expression $(a+b)^*b(a+b)$

Question

The minimum number of states in min DFA of regular expression $(a+b)^*b(a+b)$ is _____.

My attempt:

I have drawn this DFA and found the answer to be 3:

Somewhere it was explained that we need "trap" state, so the answer would be 4.

Question:

Is my DFA not correct? Can you explain it, please?

Answer 1

Here is the DFA that solves the question.

States: A, B, C, D

Arcs: (A,A,a) (A,B,b) (B,C,a) (B,D,b) (C,A,a) (C,B,b) (D,C,a) (D,D,b)

Final states: C, D

Initial state: A

(A,B,a) means that there is an arc from A to B with label a

---

That is:

Answer 2

Note that the regular language you wish to recognize can be expressed in words as "the second-last symbol of the string is $b$". As mentioned in Maczinga's comment, your proposed DFA is not correct because it does not accept $bba$. It also does accept $bab$, which it shouldn't.

---

To show that at least four states are necessary, consider any DFA over $\{a,b\}$ with three states. Since there are four length-2 strings over $\{a,b\}$, two of them must yield the same state when run on this DFA. By going through the six possibilities we will show that either exactly one of the two strings is in the language, or we can append each by the same character yielding two length-3 strings which yield the same state when run over the DFA, but of which only one is in the language.

• If $aa$ and $ab$ yield the same state, then $aaa$ and $aba$ also both yield the same state, but $aba$ is in the language while $aaa$ is not.
• If $aa$ and $ba$ yield the same state, note $ba$ is in the language, but $aa$ is not.
• If $aa$ and $bb$ yield the same state, note $bb$ is in the language, but $aa$ is not.
• If $ab$ and $ba$ yield the same state, note $ba$ is in the language, but $ab$ is not.
• If $ab$ and $bb$ yield the same state, note $bb$ is in the language, but $ab$ is not.
• If $ba$ and $bb$ yield the same state, then $baa$ and $bba$ also yield the same state, but $bba$ is in the language while $baa$ is not.

I'll leave it to you to construct a 4-state DFA which recognizes the language.