Types of Finite Automata
•Deterministic Finite Automata
•Non Deterministic Finite Automata
CAPP C12: Types of Finite Automation Slide Number 1
Deterministic Finite Automata
•A Finite Automation is termed as “deterministic”, iff for any
given state and an input symbol, the transition function ‘δ’
may lead to “one and only one next state qi” that is a
subset of Q.
CAPP C12: Types of Finite Automation Slide Number 2
Deterministic Finite Automata …
•A deterministic finite automation M(Q, Σ, q0 ,δ, F) is a five
tuple structure where
•Q is a finite set of states in which the DFA can exist.
•Σ is a set of input symbols which can be fed to the DFA.
•q0 belongs to Q is the starting state of the DFA.
CAPP C12: Types of Finite Automation Slide Number 3
Deterministic Finite Automata …
•A deterministic finite automation M(Q, Σ, q0 ,δ, F) is a five
tuple structure where …
•δ is the transition function that maps to the next state,
given the current state of DFA and the current input
symbol.
•F subset of Q is a set of final states.
CAPP C12: Types of Finite Automation Slide Number 4
Deterministic Finite Automata …
•Considering the finite automation described using the
following transition graph, we have for
a a
q1 q2
qf
q0
b
q3 q4
CAPP C12: Types of Finite Automation Slide Number 5
Deterministic Finite Automata …
•Considering the finite automation described using the
following transition graph, we have for
b a
q1 q2
qf
q0
b
q3 q4
CAPP C12: Types of Finite Automation Slide Number 6
Deterministic Finite Automata …
•Considering the finite automation described using the
following Transition Table, we have for
CAPP C12: Types of Finite Automation Slide Number 7
Deterministic Finite Automata …
Current State Input Symbol
a b
→q0 q3 q1
q1 q2 ------
q2 qf ------
q3 ------ q4
q4 ------ qf
qf ------ ------
CAPP C12: Types of Finite Automation Slide Number 8
Acceptance of String by Deterministic Finite Automata
•In a DFA, a string is said to be accepted if the transition
system stops in a final state after processing the entire
string.
•As there can be one and only one possible path for a
string in a DFA, we can definitely confirm whether the DFA
accepts the string or not.
CAPP C12: Types of Finite Automation Slide Number 9
Non Deterministic Finite Automata
•A Finite Automation is termed as “non deterministic”, iff
for any given state and an input symbol, the transition
function ‘δ’ may lead to a set of states (non Singleton Set
i.e. set having more than one member) that is a subset of
Q.
CAPP C12: Types of Finite Automation Slide Number 10
Non Deterministic Finite Automata …
•A nondeterministic finite automation M(Q, Σ, q0 ,δ, F) is a
five tuple structure where
•Q is a finite set of states in which the NFA can exist.
•Σ is a set of input symbols which can be fed to the NFA.
•q0 belongs to Q is the starting state of the NFA.
•F sub set of Q is a set of final states.
CAPP C12: Types of Finite Automation Slide Number 11
Non Deterministic Finite Automata …
•A nondeterministic finite automation M(Q, Σ, q0 ,δ, F) is a
five tuple structure where …
•δ is the transition function that maps to the next
possible set of states, given the current state of NFA and
the current input symbol. The set of output states may
be empty, may contain exactly one state or may contain
more than one state.
CAPP C12: Types of Finite Automation Slide Number 12
Non Deterministic Finite Automata …
•A nondeterministic finite automation M(Q, Σ, q0 ,δ, F) is a
five tuple structure where …
•The transition function δ maps the input Q X Σ to a set
of 2|Q| possible states.
•This set of states can be expressed by a power set of Q.
CAPP C12: Types of Finite Automation Slide Number 13
Non Deterministic Finite Automata …
•Considering the finite automation described using the
following transition graph, we have for b*baa, b*ab,
b*baab
CAPP C12: Types of Finite Automation Slide Number 14
Non Deterministic Finite Automata …
•Considering the finite automation described using the
following transition graph, we have for b*baa, b*ab,
b*baab
CAPP C12: Types of Finite Automation Slide Number 15
Non Deterministic Finite Automata …
a
q1 q2
q0 qf
q3
CAPP C12: Types of Finite Automation Slide Number 16
Non Deterministic Finite Automata …
•The transition function δ(q0 , b), there are two possibilities
i.e. q0 and q1.
•The transition function δ(q2 , a) , there are two possibilities
i.e. q3 and qf.
CAPP C12: Types of Finite Automation Slide Number 17
Non Deterministic Finite Automata …
•The Transition Table for the above Transition Graph is given
below:-
CAPP C12: Types of Finite Automation Slide Number 18
Non Deterministic Finite Automata …
Current Input Symbol
State a b
→q0 q3 {q0, q1}
q1 q2 -----
q2 {q3, qf } -----
q3 ----- qf
qf ----- -----
CAPP C12: Types of Finite Automation Slide Number 19
Acceptance of String by Non Deterministic Finite
Automata
•In a DFA, a string is said to be accepted if the transition
system stops in a final state after processing the entire
string.
•As there can be only one possible path for a string in a
DFA, one can definitely confirm whether the DFA accepts
the string or not.
•This is not the case in an NFA.
CAPP C12: Types of Finite Automation Slide Number 20
Acceptance of String by Non Deterministic Finite
Automata …
•A given string ‘w’ submitted to an NFA may have multiple
simultaneous possibilities when it follows the different
alternative paths.
•The string may be accepted in one path, rejected in
another path and not completely consumed in some other
path.
•So how does one decide the acceptability of a string?
CAPP C12: Types of Finite Automation Slide Number 21
Acceptance of String by Non Deterministic Finite
Automata …
•If among the various alternative paths there is at least one
path that leads to a final state, then the string is said to be
accepted by the NFA.
•In the NFA under our consideration, for the string “baa”
there is a possible path q0 → q1 → q2 → qf that leads to the
final state and hence the string “baa” is said to be
accepted by the NFA.
CAPP C12: Types of Finite Automation Slide Number 22
Difference between Deterministic and Non Deterministic
Finite Automata
•In DFA, for each state there is atmost one transition for
each possible input.
•In NDFA, there can be more than one transition from a
given possible input.
•In NFA, null (ϵ) moves are possible, but in DFA null (ϵ)
moves are not possible.
CAPP C12: Types of Finite Automation Slide Number 23
Limitation of Deterministic Finite Automata
•Restricted model of automatic machines.
•An abstract model of a computer science.
•Input tape is read only memory and there are finite
number of states, an FA’s memory is strictly finite.
•The FSM has only string pattern recognizing power.
CAPP C12: Types of Finite Automation Slide Number 24
Limitation of Deterministic Finite Automata …
•It is not possible to write a FSM that generates the
language a*b* i.e. the set of all strings which consists of a
series of a that is followed by the series of b of exactly
same length.
CAPP C12: Types of Finite Automation Slide Number 25
