Deterministic Finite Automata (DFA)

A deterministic finite automation is a special case of a non-deterministic finite automation (NFA) in which

  1. no state has an -transition
  2. for each state s and input symbol a, there is at most one edge labeled a leaving s.

A DFA has st most one transition from each state on any input. It means that each entry on any input. It means that each entry in the transition table is a single state (as oppose to set of states in NFA).

Because of single transition attached to each state, it is vary to determine whether a DFA accepts a given input string.

Algorithm for Simulating a DFA



The function move (S, C) gives a new state from state s on input character C.

The function 'nextchar' returns the next character in the string.

        S := S0
C := nextchar;

while not end-of-file do
        S := move (S, C)
        C := nextchar;

If S is in F then                    
        return "yes"

    return "No".

Following figure shows a DFA that recognizes the language (a|b)*abb.


The transition table is

state a b
0 1 0
1 1 2
2 1 3
3 1 0

With this DFA and the input string "ababb", above algorithm follows the sequence of states: