Courses

# 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.
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;