Deterministic finite automata

Let $\mathrm{\Sigma }$ be an alphabet. A deterministic finite automaton over $\mathrm{\Sigma }$ is a quintuple $D=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ such that:

• $Q$ is a finite set of states.
• $q_0\in Q$ is the start state.
• $F\subseteq Q$ is the set of accepting states.
• $\delta :Q\times \mathrm{\Sigma }\to Q$ is a total transition function in the sense of A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, with domain exactly the Cartesian product $Q\times \mathrm{\Sigma }$ of The Cartesian product $A\times B:=\{z\in \mathcal{P}(\mathcal{P}(A\cup B)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(a,b)\}$.

The adjective "deterministic" means that for each pair $(q,a)\in Q\times \mathrm{\Sigma }$ there is exactly one next state $\delta (q,a)$, and "finite" means that $Q$ has finite cardinality in the sense of The cardinality $\mid A\mid$ of a finite set.

• A transition diagram that omits a letter from some state does not yet specify a DFA, because totality of $\delta$ is part of the definition.

• The ambient alphabet is part of the data. The same directed graph can define different automata if the chosen alphabet changes.