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!