# Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

Let $$R=(a*)+(b*)$$ be a regular expression. Prove that there cannot exist any DFA $$M=(Q,\Sigma,\delta , q0, A)$$ such that $$|Q| = 3$$ and $$L(M)=L(R)$$.

The problem is, I think IT IS possible to construct such a dfa that has 3 states in total. Am I missing something?

• It is an "NFA", not a "DFA"! – OmG Oct 15 at 15:28
• How come? All I see is determinism here. – Mandy Oct 15 at 15:31

What you draw is an NFA, because you do not have both transition for $$a$$ and $$b$$ in two accept states. Indeed, you need 4 states at least. Because you have 4 different states:
2. Detect $$a^*$$ strings
3. Detect $$b^*$$ string
You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state with the others. Definitely you can't merge the 4th state with second and third state. Hence. the only possibility is merging the 4th state with the first state. But, we have some transitions from the initial state to other states, and if we merge the 4th and the first state, we will accept some strings that are not totally $$a$$ or $$b$$. And that is the contradiction to the definition of the language. Therefore, we need a state to go there if we found any $$b$$ in the middle of some $$a$$s or vice versa.