Why can't there be multi-state in DFA?

Question

My question is , can state3 also be named state2, or in general. Why can we name our states with same names. For the expression ab+a*a First state takes 'a'. then it will either go state2/state3.

Answer 1

A finite state machine is defined to contain (among other things) a set of states, so it makes sense for each state to be uniquely identified. The naming of states has nothing whatsoever to do with the order they might be hit.

It's not uncommon for an FSM to involve a cycle. An example would be an FSM to accept a binary string with an even number of 0's, represented by the state table below:

Input --> | 0      | 1      |
\/--State |        |        |
----------|--------|--------|
state0    | state1 | state0 |
state1    | state0 | state1 |

States: {state0, state1}
Start state: state0
Accepting states: {state0}

In that case, the machine might move from state0 to state1 and back many times. The machine's complexity would explode to infinity if we had to have a new state every time.

Answer 2

you can name your states whatever you want so long as they are uniquely identifiable.

If the states aren't different, than they shouldn't be 2 separate states in the first place

---

your particular example doesn't have any or-ing, so your regex will never use a DFA that branches like that.

But let's say you had a regex like

a(bb | cc), which can match abb or acc

ab and ac are different states, and they have to be distinguished from one-another and the output from them leads to different conclusions.

If you were at ab and you got a c than you would have to go back to the start, but If you were in the state ac and got c than you would proceed to acc and finish.