You are here
Homedeterministic finite automaton
Primary tabs
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 5tuple $(S,\Sigma,\delta,q_{0},F)$, where

$S$ is a nonempty finite set of states,

$\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:
$\UseComputerModernTips\xymatrix{\ar[r]&*+[o][F]{0}\ar[r]_{a}\ar[rd]_{b}&*+[o]% [F]{1}\ar@(r,u)[]_{a}\ar[r]_{b}&*++[o][F=]{2}\ar[dl]^{{a,b}}\\ &&*+[o][F]{3}\ar@(r,d)[]^{{a,b}}}$ 
The vertex 0 is the initial state $q_{0}$, and the vertex 2 is the only state in $F$. Note that for every vertex there is an edge leading away from it with a label for each symbol in $\Sigma$. This is a requirement of DFAs, which guarantees that operation is welldefined for any finite string.
If given the string aaab
as input, operation of the DFA above is as follows. The first a
is removed from the input string, so the edge from 0 to 1 is followed. The resulting input string is aab
. For each of the next two a
s, the edge is followed from 1 to itself. Finally, b
is read from the input string and the edge from 1 to 2 is followed. Since the input string is now $\lambda$, the operation of the DFA halts. Since it has halted in the accepting state 2, the string aaab
is accepted as a sentence in the regular language implemented by this DFA.
Now let us trace operation on the string aaaba
. Execution is as above, until state 2 is reached with a
remaining in the input string. The edge from 2 to 3 is then followed and the operation of the DFA halts. Since 3 is not an accepting state for this DFA, aaaba
is not accepted.
Remarks.

A DFA can be modified to include $\epsilon$transitionsEpsilonTransitions. But the resulting DFA can be simulated by another DFA (without any epsilon transitions).

Although the operation of a DFA is much easier to compute than that of a nondeterministic automaton, it is nontrivial to directly generate a DFA from a regular grammar. It is much easier to generate a nondeterministic finite automaton from the regular grammar, and then transform the nondeterministic finite automaton into a DFA.
Mathematics Subject Classification
68Q42 no label found68Q05 no label found03D10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections