Deterministic Finite Automaton

automata-theory

Definition

Deterministic Finite Automaton

A deterministic finite automaton (DFA) is a automaton that has a finite number of states and the transition function $\delta$ is deterministic.

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$$

where:

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet,
• $\delta :Q\times \Sigma \to Q$ is the total transition function
• $q_0\in Q$ is the initial state, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

It processes input symbols (or strings) by transitioning between states according to $\delta$ and determines acceptance based on whether the final state is in $F$.

All deterministic finite automata are nondeterministic finite automaton.

Examples

A deterministic finite automaton

The following automaton is defined by the following quintuple:

$$\begin{array}{rl}\mathcal{A}& =(Q,\Sigma ,\delta ,q_0,F)\\ & =(\{a,b,c\},\{0,1\},\delta ,a,\{a,b\})\end{array}$$

The transition function $\delta$ can be described using an operation table:

State	Symbol	Next State
$a$	$1$	$b$
$a$	$0$	$b$
$b$	$1$	$a$
$b$	$0$	$c$
$c$	$0$	$c$
$c$	$1$	$c$

Trap state

Let $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$ be a deterministic finite automaton and let $q\in Q\setminus F$ satisfy

$$\delta (q,a)=q\text{for all }a\in \Sigma .$$

Then $q$ is called a trap state.

For example, consider the following DFA:

This automaton accepts exactly

$$\{\epsilon ,00,01,10,11\}.$$

After any further symbol, the automaton enters the trap state $q_{\mathrm{trap}}$ and remains there.