## 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 := S0

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

 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:

FIGURE