Search code examples
regexdfa

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

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

Solution

  • 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.