Showing posts with label BE. Show all posts
Showing posts with label BE. Show all posts

Tuesday, 14 February 2017

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