|
A deterministic finite automaton (or DFA) is a finite-state deterministic automaton. It can be formally defined as a 5-tuple
 , where
Operation of the DFA begins at  , and movement from state to state is governed by the transition function  .  must be defined for every possible state in  and every possible symbol in  .
The way a DFA  works is as follows: when a string
 is fed nto  at starting state  ,  reads the leftmost symbol  and reaches the next state
 .  then reads the next symbol  and reaches the next state
 and reaches the next state  .  continues to read the symbols until the last symbol  is read, reaching state
 . The string  is said to be accepted by  if  , and rejected by  otherwise.
A DFA can be represented visually as a directed graph. Circular vertices denote states, and the set of directed edges, labelled by symbols in  , denotes  . The transition function takes the first symbol of the input string as, and after the transition this first symbol is removed. If the input string is  (the empty string), then the operation of the DFA is halted. If the final state when the DFA halts is in  , then the DFA can be said to have accepted the input string it was originally given. The starting state  is usually denoted by an arrow pointing to it that points from no other vertex. States in  are usually denoted by double circles.
DFAs represent regular languages, and can be used to test whether any string in  is in the language it represents. Consider the following regular language over the alphabet
 (represented by the regular expression aa*b):
This language can be represented by the following DFA.
The vertex 0 is the initial state  , and the vertex 2 is the only state in  . Note that for every vertex there is an edge leading away from it with a label for each symbol in  . This is a requirement of DFAs, which guarantees that operation is well-defined 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 as, 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  , 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.
Remark. Although the operation of a DFA is much easier to compute than that of a non-deterministic automaton, it is non-trivial to directly generate a DFA from a regular grammar. It is much easier to generate a non-deterministic finite automaton from the regular grammar, and then transform the non-deterministic finite automaton into a DFA.
| 
![$\displaystyle \UseComputerModernTips \xymatrix{ \ar[r] & *+[o][F-]{0} \ar[r]_a... ...\ar[r]_b & *++[o][F=]{2} \ar[dl]^{a,b} \ && *+[o][F-]{3} \ar@(r,d)[]^{a,b} } $](http://images.planetmath.org:8080/cache/objects/2553/l2h/img44.png "$\displaystyle \UseComputerModernTips \xymatrix{ \ar[r] & *+[o][F-]{0} \ar[r]_a... ...\ar[r]_b & *++[o][F=]{2} \ar[dl]^{a,b} \ && *+[o][F-]{3} \ar@(r,d)[]^{a,b} } $")