Skip to main content
added 101 characters in body
Source Link
OmG
  • 3.6k
  • 1
  • 14
  • 23

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.

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.

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.

Source Link
OmG
  • 3.6k
  • 1
  • 14
  • 23

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.