From NFA to DFA Subset Construction From NFA to DFA Subset Construction Converting an NFA to a DFA Civil Engineering (CE) Notes | EduRev

Civil Engineering (CE) : From NFA to DFA Subset Construction From NFA to DFA Subset Construction Converting an NFA to a DFA Civil Engineering (CE) Notes | EduRev

 Page 1


From NFA to DFA 
Subset Construction 
Page 2


From NFA to DFA 
Subset Construction 
Converting an NFA to a DFA 
? Let’s convert the following NFA for the regular 
expression (a|b)*aa to a DFA.  
Page 3


From NFA to DFA 
Subset Construction 
Converting an NFA to a DFA 
? Let’s convert the following NFA for the regular 
expression (a|b)*aa to a DFA.  
Subset Construction  
? Subset construction is a technique for 
constructing a DFA from an NFA.  
? Central to this algorithm is the calculation of 
the e-closure of a state s.   
? Simply put, the e-closure of s is the set of all 
states reachable from s by following 0 or more 
e-transitions.  
? The e-closure of a set of states is the union of 
the e-closures of each state in the set.  
Page 4


From NFA to DFA 
Subset Construction 
Converting an NFA to a DFA 
? Let’s convert the following NFA for the regular 
expression (a|b)*aa to a DFA.  
Subset Construction  
? Subset construction is a technique for 
constructing a DFA from an NFA.  
? Central to this algorithm is the calculation of 
the e-closure of a state s.   
? Simply put, the e-closure of s is the set of all 
states reachable from s by following 0 or more 
e-transitions.  
? The e-closure of a set of states is the union of 
the e-closures of each state in the set.  
Subset Construction  
? We begin by calculating e-closure(s
0
), where s
0
 is the 
start state of NFA N.  
? In the NFA below, e-closure(0) = {0,1,2,4,7}. This set 
is the start state for the DFA D.  
 
Page 5


From NFA to DFA 
Subset Construction 
Converting an NFA to a DFA 
? Let’s convert the following NFA for the regular 
expression (a|b)*aa to a DFA.  
Subset Construction  
? Subset construction is a technique for 
constructing a DFA from an NFA.  
? Central to this algorithm is the calculation of 
the e-closure of a state s.   
? Simply put, the e-closure of s is the set of all 
states reachable from s by following 0 or more 
e-transitions.  
? The e-closure of a set of states is the union of 
the e-closures of each state in the set.  
Subset Construction  
? We begin by calculating e-closure(s
0
), where s
0
 is the 
start state of NFA N.  
? In the NFA below, e-closure(0) = {0,1,2,4,7}. This set 
is the start state for the DFA D.  
 
Subset Construction 
? Another operation in subset construction is 
move(S,a), where S is a set of NFA states 
and a is an input character.   
? move(S,a) is a set of NFA states to which 
there is a transition on input symbol a from 
some NFA state s in S.  
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Semester Notes

,

pdf

,

Previous Year Questions with Solutions

,

past year papers

,

Sample Paper

,

From NFA to DFA Subset Construction From NFA to DFA Subset Construction Converting an NFA to a DFA Civil Engineering (CE) Notes | EduRev

,

From NFA to DFA Subset Construction From NFA to DFA Subset Construction Converting an NFA to a DFA Civil Engineering (CE) Notes | EduRev

,

From NFA to DFA Subset Construction From NFA to DFA Subset Construction Converting an NFA to a DFA Civil Engineering (CE) Notes | EduRev

,

ppt

,

Important questions

,

Objective type Questions

,

Exam

,

Viva Questions

,

Extra Questions

,

mock tests for examination

,

video lectures

,

shortcuts and tricks

,

Summary

,

study material

,

MCQs

,

Free

,

practice quizzes

;