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: