CSE322
DFA and NDFA
Lecture #3
Nondeterministic Finite Automaton
Alphabet =
{a}
q1 a q2
a
q0
a
q3
Alphabet =
{a}
Two choices
q1 a q2
a
q0
a
q3
Alphabet =
{a}
Two choices
q1 a q2 No transition
a
q0
a
q3 No transition
NFA
example
Real-Life Examples of DFA (Deterministic Finite
Automaton)
• Vending Machine
• Password Validation System
• Traffic Light System
• Spell Checker
• Elevator Control System
Real-Life Examples of NFA (Nondeterministic
Finite Automaton)
• Regular Expression Matching
• Game Level Navigation
• Network Packet Routing
• Search Engine Query Processing
• Robot Navigation in a Maze
Summary of Differences:
•
• DFA: For each input symbol, there is exactly one state to transition to,
making the system deterministic.
• NFA: For each input symbol, there may be multiple possible states to
transition to, allowing for non-determinism in processing inputs.
differences between DFA and NDFA.
Equivalence of DFA and
NDFA
Acceptablity
• NFAs and DFAs are equivalent in that if a
language is recognized by an NFA, it is also
recognized by a DFA and vice versa
DFA and NDFA
• Every NDFA is DFA but vice versa is not true
Equivalence of DFA and NDFA
Problem
Solution
Problem
Solution
• There are maximum 2n DFA possible if we
convert NDFA to DFA.
NFA TO DFA
Using the above algorithm, we find its equivalent DFA. The state
table of the DFA is shown in below.
• Which statement is correct?
(a) All NFAs are DFAs.
(b) All NFAs are not DFAs.
(c) both a and b
(d) None of these
• Which statement is correct?
(a) All NFAs are DFAs.
(b) All NFAs are not DFAs.
(c) both a and b
(d) None of these
• For each symbolic representation of the
alphabet, there is only one state transition
in?
(a) FA
(b) NFA
(c) DFA
• (d) All of these
• For each symbolic representation of the
alphabet, there is only one state transition
in?
(a) FA
(b) NFA
(c) DFA
• (d) All of these
• Which of the following cannot use Empty
String transition?
• (a) FA
(b) NFA
(c) DFA
• (d) All of these
• Which of the following cannot use Empty
String transition?
• (a) FA
(b) NFA
(c) DFA
• (d) All of these
• Which of the following can use Empty String
transition?
• (a) FA
(b) NFA
(c) DFA
• (d) All of these
• Which of the following can use Empty String
transition?
• (a) FA
(b) NFA
(c) DFA
• (d) All of these
• Dead state may be required in which of the
following?
(a) FA
(b) NFA
(c) DFA
• (d) All of these
• Dead state may be required in which of the
following?
(a) FA
(b) NFA
(c) DFA
• (d) All of these
• The total time needed to run any input string
in DFA is ……. than time required in NFA.
(a) more
• (b) Less
• (c) equal
• (d) None of these
• The total time needed to run any input string
in DFA is ……. than time required in NFA.
(a) more
• (b) Less
• (c) equal
• (d) None of these
• Which statement is correct about DFA?
(a) All DFAs are derived from NFAs.
(b) All NFAs are derived from DFAs.
(c) Both can’t be derived from each other
• (d) Both a and b
• Which statement is correct about DFA?
(a) All DFAs are derived from NFAs.
(b) All NFAs are derived from DFAs.
(c) Both can’t be derived from each other
• (d) Both a and b
