We start with a formal definition of a deterministic finite automaton.

Definition: Deterministic Finite Automaton (DFA)

A deterministic finite automaton DFA) is a tuple $A=(C,\Sigma,\delta,F,s_0)$, containing

We say that the DFA accepts an input word $\omega$ if and only if the DFA reaches a final condition $f\in F$ after consuming $\omega.$

The formal language $L(\operatorname{DFA})$ accepted by the DFA can be defined as a set of all words over the alphabet $\Sigma$, for which the image of function compositions of $\delta$ is contained in $F,$ formally: $$L(\operatorname{DFA}):=\{\sigma_0\sigma_1\ldots\sigma_n\in\Sigma^*\mid \delta(\ldots\delta(\delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)\in F\}.$$

The class of all languages accepted by a DFA is denoted by $\mathcal L(\operatorname{DFA})$.


Applications: 1
Corollaries: 2
Definitions: 3 4
Examples: 5 6
Proofs: 7 8
Theorems: 9 10

Thank you to the contributors under CC BY-SA 4.0!




  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015