## Deterministic Finite Automata (DFA)

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

- no state has an
-transition
- 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_{0
}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

###