5
$\begingroup$

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

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

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0
-1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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, 2014 at 14:07
  • $\begingroup$ I've edited it as 'respective states' $\endgroup$
    – Terminal
    Feb 6, 2014 at 14:07
  • $\begingroup$ I saw the edit. I still don't understand what you mean. $\endgroup$
    – David Richerby
    Feb 6, 2014 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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