Saturday, January 29, 2011

Finite Automata

Finite Automata (FA) :
  • A Finite Automaton provides the simplest model of a computing device.
  • It has a central processor of finite capacity and it is based on the concept of state.
  • There are two different types of Finite Automata.
                  (1) Deterministic Finite Automata (DFA) 
                  (2) Non-Deterministic Finite Automata (NFA)

Symbols used for Finite Automata

Characteristics of DFA:
  • Out-degree of each state is equal to number of alphabets in a Language.
  • For each alphabet in a language there must be one transition.
Relation between DFA and NFA:

  • Every DFA is subset of it its equivalent NFA.
  • So we can say that "Every DFA is a NFA but reverse is not true"