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

  • $\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.

| cite | improve this answer | |
  • 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.