Tuesday, 14 February 2017

Difference between Deterministic Finite Automata & Non Deterministic Finite Automata

DETERMINISTIC FINITE STATE AUTOMATA
NON DETERMINISTIC FINITE STATE AUTOMATA
It is a finite-state machine that accepts and rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string.
It is a finite-state machine that accepts and rejects strings of symbols and produces a number of computation (or run) of the automaton for each input string.
It consist of 5 tuple:
     L = {Q, q0, ∑, F, Δ }
It consist of 5 tuples:
     L = {Q, q0, ∑, F, Δ }
Transition Function is 
       Δ : Q × Σ → Q
Transition Function is 
     Δ : Q × Σ → 2Q
Only one transition is possible for single input symbol from any states
Many transition is possible for single input symbol from any states
No transition can occur without consuming any input symbol
Transition may occur without consuming any
input symbol known as NFA-Ԑ transition
It can represent only limited number of regular expression
It can be used to represent large number of regular expression

Difference Between Finite Automata and Push down Automata

FINITE AUTOMATA
PUSHDOWN AUTOMATA
A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set
A pushdown automaton (PDA) is a type of automaton that employs a stack.
It doesn’t has the capability to store long sequence of input alphabets
It has stack to store the input alphabets
Finite Automata can be constructed for Type-3 grammar
Pushdown Automata can be constructed for Type-2 grammar
Input alphabets are accepted by reaching “final states”
Input alphabets are accepted by reaching :
1.     Empty stack
2.     Final state
NFA can be converted into equivalent DFA
NPDA has more capability than DPDA
It consist of 5 tuples:
L = {Q, q0, ∑, F, σ}
It consists of 7 tuples:
L = {Q, q0, ∑, F, ᴦ, σ, z0  }
Finite automata can be constructed for regular language
Pushdown automata can be constructed for context free grammar