◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Definition: Deterministic Finite Automaton (DFA)

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

• a finite set $C$ of conditions (or states),
• a finite input alphabet $\Sigma$,
• the state transition function $\delta:C\times\Sigma\to C$,
• the set of final states $F\subseteq C$, and
• the starting condition $s_0.$

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})$.

Notes

• The DFA is an acceptor since it has no output, only input.
• It starts at the starting condition $s_0.$
• An input word $\omega=\sigma_0\sigma_1\ldots\sigma_n$ changes the states of the DFA by the formula $s_{i+1}:=\delta(s_i,\sigma_i)$. In other words, the transition function $\delta$ calculates for each symbol $\sigma_i$, given the current state $s_i$, the new state $s_{i+1}.$
• The DFA is always deterministic, since $\delta$ is a function (it is right-unique, the new state $s_{i+1}$ is always completely determined by the current state $s_i$ and the current symbol $\sigma_i.$)
• Whether or not the DFA accepts the empty word $\epsilon\in\Sigma^*$ can be read immediately from the definition of the DFA. This is the case if and only if $s_0\in F$, i.e. the starting condition is also one of its final states.

Mentioned in:

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!

Github:

References

Bibliography

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