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.

Example

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$