patternMinor
Can a DFA have two symbols on one arrow?
Viewed 0 times
candfaarrowtwoonehavesymbols
Problem
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).
This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).
Solution
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.
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.
Context
StackExchange Computer Science Q#21373, answer score: 6
Revisions (0)
No revisions yet.