I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and $q_1$, can I have one arrow from $q_0$ to $q_1$ with both $a$ and $b$?

This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).

  • $\begingroup$ Yes. That's just the same thing as having two arrows, one labelled $a$ and one labelled $b$. $\endgroup$ – David Richerby Feb 6 '14 at 14:04

The transition graph (as a drawing) is merely a representation of an Automaton, which is a well-defined model.

Formally, an DFA is a tuple $(Q,\Sigma,\delta,q_0,F)$, where the "type" of the transition function is $\delta:Q\times \Sigma\to Q$.

Thus, if you have $\delta(q_0,a)=\delta(q_0,b)=q_1$, that's fine. In the graphic representation, you will either have two arrows from $q_0$ to $q_1$, labeled $a$ and $b$, or you can just put both letters on the same arrow, it's not a formal thing anyway.


As long as the starting and ending of respective states are same you can add as many symbols. enter image description here

  • $\begingroup$ I don't understand what you mean. An arrow by definition goes from one state to another state. How could an arrow not have the same start and end state as itself? $\endgroup$ – David Richerby Feb 6 '14 at 14:07
  • $\begingroup$ I've edited it as 'respective states' $\endgroup$ – Terminal Feb 6 '14 at 14:07
  • $\begingroup$ I saw the edit. I still don't understand what you mean. $\endgroup$ – David Richerby Feb 6 '14 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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