# deterministic finite automaton

A deterministic finite automaton (or DFA) is a deterministic automaton with a finite input alphabet and a finite number of states. It can be formally defined as a 5-tuple $(S,\Sigma,\delta,q_{0},F)$, where

• $S$ is a non-empty finite set of states,

• $\Sigma$ is the alphabet (defining what set of input strings the automaton operates on),

• $\delta:S\times\Sigma\rightarrow S$ is the transition function,

• $q_{0}\in S$ is the starting state, and

• $F\subseteq S$ is a set of final (or accepting states).

A DFA works exactly like a general automaton: operation begins at $q_{0}$, and movement from state to state is governed by the transition function $\delta$. A word is accepted exactly when a final state is reached upon reading the last (rightmost) symbol of the word.

DFAs represent regular languages, and can be used to test whether any string in $\Sigma^{*}$ is in the language it represents. Consider the following regular language over the alphabet $\Sigma:=\left\{\verb.a.,\verb.b.\right\}$ (represented by the regular expression aa*b):

 $\displaystyle\verb.<.S\verb.>.$ $\displaystyle\verb.::=.$ $\displaystyle\verb=a=\,A$ $\displaystyle\verb.<.A\verb.>.$ $\displaystyle\verb.::=.$ $\displaystyle b\,\verb.|.\,\verb=a=\,A$

This language can be represented by the DFA with the following state diagram: