Search code examples
dfa

Can a DFA state have two arrows pointing to it with the same value?

I know that to be considered a DFA, each state cannot have more than one arrow with the same value pointing to another state. However, can a DFA have a state that has two arrows pointing to it with the same value?

Solution

  • Sure. As long as each response is deterministic, several states might go to the same state on the same next input. Since you can only be in one of the states, determinism isn't lost.

        x
A ----> B
|       |
|y      |z
|       |
V   z   V
C ----> D