The DFA is a 5-tuple ($Q,\sum, \delta, q_0, F$) where

-finite set of states ($Q$)
-finite set of symbols called the alphabet ($\sum$)
-a transition function ($\delta: Q \times \sum \rightarrow Q$)
-an initial or start state ($q_0 \in Q$)
-a set of accept states ($F \subset Q$)

Since in practice (programmatic implementation) the transition "production" (that is, $\delta(q_{from}, input) = q_{to}$) cannot be the same for all in $Q\times \sum$ and $Q$, then why is it not defined as "a set of transitions".


closed as unclear what you're asking by Anton Trunov, vonbrand, David Richerby, Juho, Evil Jan 1 '16 at 22:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Downvoters, please comment on how the question can be improved. (If you don't think it can be made suitable, you should have voted to close.) $\endgroup$ – Raphael Dec 29 '15 at 19:59
  • 3
    $\begingroup$ You should explain the "cannot be the same ...". I read it now 10 times and it still sounds like "1 cannot be equal to 2 so the moon is made of cheese". Sorry :-( $\endgroup$ – Harald Dec 29 '15 at 20:07

A function is a set -- a set with additional structure. A function $f: X \to Y$ can be thought of as a subset of $X \times Y$, i.e., as a set $S$ of pairs $(x,y)$ such that $f(x)=y$. However, it's not just any old set. To qualify as a function, it has to have the additional property that $f(x)$ has a single value. Put another way, the set $S$ cannot contain two elements $(x,y)$, $(x,y')$ such that $y \ne y'$: a function is a set $S$ where that never happens.

The same applies here. The transition function is a set (a subset of $Q \times \Sigma \times Q$), but a set with some additional properties/restrictions that must hold for this to qualify as a DFA.

So, it's defined as a function to emphasize the additional requirement that for each state $q$ and each symbol $s$, there is a single state $q'$ that you go to, i.e., a single transition out of $q$ on symbol $s$.

If there were multiple possible states you could go to, from $q$ when receiving symbol $s$, then it wouldn't be a deterministic finite automaton -- it'd be a non-deterministic finite automaton.

  • 1
    $\begingroup$ Again... You were faster and provided better answer. Cheers. There is nothing more to do than cleanup. $\endgroup$ – Evil Dec 29 '15 at 19:11

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