Posts

Showing posts from January 23, 2011

Finite Automata

Image
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"