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
|
Tuesday, 14 February 2017
Difference between Deterministic Finite Automata & Non Deterministic Finite Automata
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
|
Subscribe to:
Posts (Atom)