1

COMPILER CONSTRUCTION(CS-636)

Gul Sher Ali

MS(CS & Tech.)-China

______________________________________________________
GIMS- PMAS Arid Agriculture University, Gujrat Campus
Lecture 5 2

 NFA- DFA conversion for NFA’s where there is no epsilon

consumption. (*method descirbed on white board)

Lecture 6 (Upcoming Slides)

NFA → DFA Construction 3

 The algorithm is called subset construction.

 In the transition table of an NFA, each entry is a set of states.
 In DFA, each entry is a single state
NFA → DFA Construction 4

 The general idea behind

NFA-to-DFA construction
is that each DFA state
corresponds to a set of
NFA states.
NFA → DFA Construction 5

 TheDFA uses its state to

keep track of all possible
states the NFA can be in
after reading each input
symbol.
NFA → DFA Construction 6

 We will use the following

operations.
e-closure(T):
set of NFA states
reachable from some
NFA state s in T on e-
transitions alone.
NFA  DFA Construction 7

 move(T,a):
set of NFA states to which
there is a transition on
input a from some NFA
state s in set of states T.
NFA → DFA Construction 8

 Beforeit sees the first input

symbol, NFA can be in
any of the state in the set
e-closure(s0), where s0 is
the start state of the NFA.
NFA → DFA Construction 9

 Suppose that exactly the

states in set T are
reachable from s0 on a
given sequence of input
symbols.
NFA → DFA Construction 10

 Let a be the next input

symbol.
 On seeing a, the NFA can
move to any of the states
in the set move(T,a).
NFA → DFA Construction 11

 Let a be the next input

symbol.
 On seeing a, the NFA can
move to any of the states
in the set move(T,a).
NFA → DFA Construction 12

 When we allow for

e-transitions, NFA can be
in any of the states in
e-closure(move(T,a))
after seeing a.
Subset Construction 13

Algorithm:
Input:
NFA N with state set S,
alphabet S, start state
s0, final states F
Subset Construction 14

Output:
DFA D with state set
S’, alphabet S, start
states
s0’ = e-closure(s0),
final states F’,
transition
table: S’ x S → S’
Subset Construction Example
15
e
a
2 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
NFA for (a | b )*abb
 e
a 16
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 The start state of equivalent DFA is e-closure(0), which is
A = {0,1,2,4,7}
 e
a 17
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 A = {0,1,2,4,7}, these are exactly the states reachable from
state 0 via e-transition.
 e
18
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 The input symbol alphabet here is {a,b}.
 e
19
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 The algorithm tells us to mark A and then compute
e-closure(move(A,a))
 e
a 20
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 move(A,a)), is the set of states of NFA that have transition on
‘a’ from members of A.
 e 21
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 Only 2 and 7 have such transition, to 3 and 8.
 e
22
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 So, e-closure(move(A,a)) =
e-closure({3,8}) =
{1,2,3,4,6,7,8}
 e 23
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 Let B = {1,2,3,4,6,7,8}.
 Thus Dtran[A,a] = B
 e 24
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 For input b, among states in A, only 4 has transition on b to 5
 e
25
2e a 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 C = e-closure({5})
= {1,2,4,5,6,7}
 Thus, Dtran[A,b] = C
 e
26
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 We continue this process with the unmarked sets B and C
 e
27
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 i.e., e-closure(move(B,a)),
e-closure(move(B,b)),
 e
28
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 e-closure(move(C,a)) and
e-closure(move(C,b))
 e 29
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 Until all sets and states of DFA are marked.
 e
30
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 This is certain since there are only 211 (!) different subsets of a
set of 11 states.
 e 31
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e e
b
4 5
e
 And a set, once marked, is marked forever.
Subset Construction 32
Eventually, the 5 sets are:
A={0,1,2,4,7}
B={1,2,3,4,6,7,8}
C={1,2,4,5,6,7}
D={1,2,4,5,6,7,9}
E={1,2,4,5,6,7,10}
 e 33
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e b
e
4 5
e
A is start state
A={0,1,2,4,7} D={1,2,4,5,6,7,9}
B={1,2,3,4,6,7,8} E={1,2,4,5,6,7,10}
C={1,2,4,5,6,7}
 e 34
a
2e 3
e e
e e a b b
0 1 6 7 8 9 10
e b
e
4 5
e
E is accepting state
A={0,1,2,4,7} D={1,2,4,5,6,7,9}
B={1,2,3,4,6,7,8} E={1,2,4,5,6,7,10}
C={1,2,4,5,6,7}
Resulting DFA 35
a a
a b b
A B D E
a
b a
b
C

b
DFA for (a | b )*abb
Resulting DFA 36
a a
a b b
A B D E
a
b a
b
C

b a a a a b b
Final Transition Table
Input symbol
State a b
A B C
B B D
C B C
D B E
E B C
37