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. enter image description here

Am I missing something?

  • 1
    $\begingroup$ It is an "NFA", not a "DFA"! $\endgroup$ – OmG Oct 15 '19 at 15:28
  • $\begingroup$ How come? All I see is determinism here. $\endgroup$ – Mandy Oct 15 '19 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:

  1. Initial state
  2. Detect $a^*$ strings
  3. Detect $b^*$ string
  4. None of them

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks I totally forgot about trap states! $\endgroup$ – Mandy Oct 15 '19 at 16:14
  • $\begingroup$ @Mandy my pleasure. $\endgroup$ – OmG Oct 15 '19 at 16:59

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.