3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It is an "NFA", not a "DFA"! $\endgroup$
    – OmG
    Commented Oct 15, 2019 at 15:28
  • $\begingroup$ How come? All I see is determinism here. $\endgroup$
    – Mandy
    Commented Oct 15, 2019 at 15:31

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks I totally forgot about trap states! $\endgroup$
    – Mandy
    Commented Oct 15, 2019 at 16:14
  • $\begingroup$ @Mandy my pleasure. $\endgroup$
    – OmG
    Commented Oct 15, 2019 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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