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

INPUT:

• string x
• a DFA with start state, so . . .
• a set of accepting state's F.

OUTPUT:

• The answer 'yes' if D accepts x; 'no' otherwise.

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.

Initialization:
        S := S₀
          C := nextchar;

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

If S is in F then                    
        return "yes"

else
    return "No".

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

FIGURE

The transition table is

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

FIGURE