NFA construction and Minimum DFA

1
Conversion : NFA  DFA Algorithm

• Algorithm Constructs a Transition Table for DFA from NFA.

• Each state in DFA corresponds to a SET of states of the NFA.
• Why does this occur ? and for this reason,
we call this subset
•  moves construction
• non-determinism
Both require us to characterize multiple situations that occur for
accepting the same string.
(Recall : Same input can have multiple paths in NFA)
• Key Issue : Reconciling AMBIGUITY !

2
Converting NFA to DFA – 1st Look


a 3 b 4
2
 
0  1 5  8
 

6 c 7


From State 0, Where can we move without consuming any input ?
This forms a new state: 0,1,2,6,8 What transitions are defined for this
new state ?
3
 The Resulting DFA
a

0, 1, 2, 6, 8 a 3
a
c b

1, 2, 5, 6, 7, 8
c 1, 2, 4, 5, 6, 8

c
Which States are FINAL States ?
a
A How do we handle
B
a alphabet symbols not
a b
c defined for A, B, C, D ?
D
c C
c
4
 Algorithm Concepts
NFA N = ( Q, , q0,  , F )
-Closure(q) : q  Q
: set of states in Q that are reachable
No input is from q via -moves of N that originate
consumed
from s.
-Closure(T) : T  Q
: NFA states reachable from all t  T
on -moves only.
(T, a) : T  Q, a  
: Set of states to which there is a
transition on input a from some t  T

These 3 operations are utilized by algorithms

techniques to facilitate the conversion process.
5
 Illustrating Conversion – An Example
Start with NFA:  (a | b)*abb

2 3
 a 

start  a
0 1 6  7 8 b 9

  b
b
4 5 10

First we calculate: -closure(0) (i.e., state 0)

-closure(0) = {0, 1, 2, 4, 7} (all states reachable from 0
on -moves)
Let A={0, 1, 2, 4, 7} be a state of new DFA, D.
6
Conversion Example – continued (1)
2nd , we calculate : a : -closure((A,a)) and
b : -closure((A,b))
a : -closure((A, a)) = -closure(({0,1,2,4,7},a))}
adds {3,8} ( since (2,a) = 3 and (7,a)=8)

From this we have : -closure({3,8}) = {1,2,3,4,6,7,8}

(since 36 1 4, 6 7, and 1 2 all by -moves)
Let B={1,2,3,4,6,7,8} be a new state. Define Dtran[A,a] = B.

b : -closure((A,b)) = -closure(({0,1,2,4,7},b))
adds {5} ( since move(4,b)=5)

From this we have : -closure({5}) = {1,2,4,5,6,7}

(since 56 1 4, 6 7, and 1 2 all by -moves)
Let C={1,2,4,5,6,7} be a new state. Define Dtran[A,b] = C.
7
Conversion Example – continued (2)
3rd , we calculate for state B on {a,b}
a : -closure((B, a)) = -closure(({1, 2, 3, 4, 6, 7, 8},a))}
= {1,2,3,4,6,7,8} = B
Define Dtran[B, a] = B.

b : -closure((B,b)) = -closure(({1, 2, 3, 4, 6, 7,8 },b))}

= {1, 2, 4, 5, 6, 7, 9 } = D
Define Dtran[B, b] = D.

4th , we calculate for state C on {a, b}

a : -closure((C,a)) = -closure(({1,2,4,5,6,7},a))}
= {1,2,3,4,6,7,8} = B
Define Dtran[C, a] = B.

b : -closure((C,b)) = -closure(({1,2,4,5,6,7},b))}
= {1,2,4,5,6,7} = C
Define Dtran[C, b] = C.
8
Conversion Example – continued (3)
5th , we calculate for state D on {a,b}
a : -closure((D, a)) = -closure(({1,2,4,5,6,7,9},a))}
= {1,2,3,4,6,7,8} = B
Define Dtran[D, a] = B.

b : -closure((D,b)) = -closure(({1,2,4,5,6,7,9},b))}
= {1,2,4,5,6,7,10} = E
Define Dtran[D, b] = E.

Finally, we calculate for state E on {a, b}

a : -closure((E, a)) = -closure(({1,2,4,5,6,7,10},a))}
= {1,2,3,4,6,7,8} = B
Define Dtran[E, a] = B.

b : -closure((E,b)) = -closure(({1,2,4,5,6,7,10},b))}
= {1,2,4,5,6,7} = C
Define Dtran[E,b] = C.
9
Conversion Example – continued (4)
This gives the transition table Dtran for the DFA of:

Input Symbol
Dstates a b
A B C
B B D
C B C
D B E
E* B C

b C b
a
start a b b
A B D E
a
a a
10
Algorithm For Subset Construction
push all states in T onto stack;
initialize -closure(T) to T;
while stack is not empty do begin
pop t, the top element, off the stack;
for each state u with edge from t to u labeled  do
if u is not in -closure(T) do begin
add u to -closure(T) ;
push u onto stack
end
end 11
Algorithm For Subset Construction – (2)

initially, -closure(q0) is only (unmarked) state in Dstates;

while there is unmarked state T in Dstates do begin
mark T;
for each input symbol a do begin
U := -closure((T, a));
if U is not in Dstates then
add U as an unmarked state to Dstates;
Dtran[T,a] := U
end
end 12
 Regular Expression to NFA
Construction
We now focus on transforming a Reg. Expr. to an NFA
This construction allows us to take:
• Regular Expressions (which describe tokens)
• To an NFA (to characterize language)
• To a DFA (which can be “computerized”)
The construction process is component-wise
Builds NFA from components of the regular expression
in a special order with particular techniques.
NOTE: Construction is “syntax-directed” translation, i.e., syntax of
regular expression is determining factor for NFA construction and
structure.
13
Motivation: Construct NFA For:
:

a:

b:

ab:

 | ab :

a*

( | ab )* :

14
Motivation: Construct NFA For:
: start i  f
a:
start 0 1
a
b: start b
A B

ab: start a
0 1  A b B
 | ab :

a*

( | ab )* :
15
 Construction Algorithm :
R.E.  NFA
Construction Process :
1st : Identify subexpressions of the regular expression

 symbols
r|s
rs
r*

2nd : Characterize “pieces” of NFA for each subexpression

16
 Piecing Together NFAs

1. For  in the regular expression, construct NFA

start
i f L()


2. For a   in the regular expression, construct NFA

start
i f L(a)
a

17
 Piecing Together NFAs – continued(1)
3.(a) If s, t are regular expressions, N(s), N(t) their NFAs s|t
has NFA:

N(s) 
start i 
f L(s)  L(t)


N(t)

where i and f are new start / final states, and -moves are
introduced from i to the old start states of N(s) and N(t) as
well as from all of their final states to f.

18
 Piecing Together NFAs – continued(2)
3.(b) If s, t are regular expressions, N(s), N(t) their NFAs st
(concatenation) has NFA:

start
i N(s) N(t) f L(s) L(t)

overlap
Alternative:

start i    f
N(s) N(t)

where i is the start state of N(s) (or new under the

alternative) and f is the final state of N(t) (or new). Overlap
maps final states of N(s) to start state of N(t).
19
Piecing Together NFAs – continued(3)
3.(c) If s is a regular expressions, N(s) its NFA, s* (Kleene
star) has NFA:


start i   f
N(s)

where : i is new start state and f is new final state

-move i to f (to accept null string)
-moves i to old start, old final(s) to f
-move old final to old start (WHY?)

20
 Properties of Construction
Let r be a regular expression, with NFA N(r), then

1. N(r) has #of states  2*(#symbols + #operators) of r.

2. N(r) has exactly one start and one accepting state.

3. Each state of N(r) has at most one outgoing edge a.

or at most two outgoing ’s

4. BE CAREFUL to assign unique names to all states !

21
 Pulling Together Concepts
• Designing Lexical Analyzer Generator
Reg. Expr.  NFA construction
NFA  DFA conversion
DFA simulation for lexical analyzer
• Recall Lex Structure
(a | b)*abb
Pattern Action 
e.g.
Pattern Action 
(abc)*ab
… … 
etc.
Recognizer!
- Each pattern recognizes lexemes
- Each pattern described by regular expression
22
 Example
P1 : a
P2 : abb 3 patterns
P3 : a*b+

NFA’s :
start a P1
1 2
P2
start a b b
3 4 5 6

a b
start P3
7 8
b

23
 Example – continued (2)
Combined NFA :
a
1 2 P1


 a b b
0 3 4 5 6 P2
start
a b

P3
7 8
b

Examples a a b a
{0,1,3,7} {2,4,7} {7} {8} death
pattern matched: - P1 - P3 -
a b b
{0,1,3,7} {2,4,7} {5,8} {6,8} break tie in
pattern matched: - P1 P3 P2,P3  favor of P2

24
 Example – continued (3)
Alternatively Construct DFA: (keep track of correspondence
between patterns and new accepting states)

Input Symbol
STATE a b Pattern
{0,1,3,7} {2,4,7} {8} none
{2,4,7} {7} {5,8} P1
{8} - {8} P3
{7} {7} {8} none
{5,8} - {6,8} P3
break tie in
{6,8} - {8} P2 favor of P2

25
Minimizing the Number of States of
DFA
1. Construct initial partition  of S with two groups:
accepting/ non-accepting.
2. (Construct new )For each group G of  do begin
1. Partition G into subgroups such that two states s,t
of G are in the same subgroup iff for all symbols a
states s, t have transitions on a to states of the same
group of .
2. Replace G in new by the set of all these subgroups.
3. Compare new and . If equal, final:=  then proceed to 4,
else set  := new and goto 2.
4. Aggregate states belonging in the groups of final

26
 A Detailed Example
The DFA for ( a | b )* abb
Character
a a State a b

a b b s0 s1 s2
s0 s1 s3 s4 s1 s1 s3

a s2 s1 s2
b a b
s3 s1 s4
s2 s4* s1 s2

 Not much expansion from NFA (we feared exponential blowup)

 Deterministic transitions
 Use same code skeleton as before

27
 A Detailed Example (DFA Minimization)

Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4}

{s0,s1,s2,s3}

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

28
 A Detailed Example (DFA Minimization)

Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none

{s0,s1,s2,s3}

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

29
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3} {s0,s1,s2}

{s0,s1,s2,s3}

Character
State a b
s0 s1 s2
a a
s1 s1 s3
a b b
s0 s1 s3 s4
s2 s1 s2
b a a b s3 s1 s4
s2
s4* s1 s2
b

30
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s0,s1,s2,s3} {s4} none {s3} {s0,s1,s2}

P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2}

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

31
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3} {s0,s1,s2}

{s0,s1,s2,s3}
P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

32
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on Split on b
a
P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3}
{s0,s1,s2,s3} {s0,s1,s2}
P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none {s1} {s0,s2}

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

33
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3} {s0,s1,s2}

{s0,s1,s2,s3}
P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none {s1} {s0,s2}

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2}

Character
State a b
s0 s1 s2
a a
a b b s1 s1 s3
s0 s1 s3 s4
s2 s1 s2
b a a b
s3 s1 s4
s2
s4* s1 s2
b

34
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3} {s0,s1,s2}

{s0,s1,s2,s3}
P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none {s1} {s0,s2}

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2} {s1} none none

Character
State a b
a a s0 s1 s2
a b b
s0 s1 s3 s4 s1 s1 s3
b a a b s2 s1 s2
s2 s3 s1 s4
b s4* s1 s2

35
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s0,s1,s2,s3} {s4} none {s3} {s0,s1,s2}

P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none {s1} {s0,s2}

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2} {s1} none none

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2} {s0,s2} none none

Character
State a b
a a
Empty worklist s0 s1 s2
s0
a
s1
b
s3
b
s4
done! s1 s1 s3

b a a s2 s1 s2
b
s2 s3 s1 s4

b s4* s1 s2

36
 A Detailed Example
(DFA Minimization)
Current Partition Worklist s Split on a Split on b

P0 {s4} {s0,s1,s2,s3} {s4} {s4} none {s3} {s0,s1,s2}

{s0,s1,s2,s3}
P1 {s4} {s3} {s0,s1,s2} {s3} {s0,s1,s2} {s3} none {s1} {s0,s2}

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2} {s1} none none

P2 {s4} {s3} {s1} {s0,s2} {s1} {s0,s2} {s0,s2} none none

a a b a
a
a b b a b b
s0 s1 s3 s4 s1 s3 s4
s0 , s2
b a a b a b
s2

37
 DFA Minimization

What about a ( b | c )* ?
b
 q4 q5 
q0
a
q1  q2  q3 q8  q9
 q6 c 
q7


First, States
the subset construction:
-closure((s,*))
DFA NFA a b c b

s0 q0 s1 none none s2
b
q1, q2, q3, a
s2 s3 s0 s1 b c
s1 q 4 , q6 , q9 none
c
s3
q 5 , q8 , q9 ,
s2 q 3 , q4 , q6 none s2 s3
c

s3 q 7 , q8 , q9 ,
q 3 , q4 , q6 none s2 s3

38
 Example (solve it yourself !!!)
a
a
A a F
B
a b
b a
D
C
b

b b

a a
A,C,D
Minimized DFA: B,F

b
b

39
 From NFA to DFA
• We need some method for eliminating ε-transitions
and multiple transitions from a state on a single
input character.
• Eliminating -transitions involves the construction
of -closures.
• Eliminating multiple transitions involves keeping
track of the set of the states instead of single states.

40
  - Closure

• -closure of a single state q is the set of states

reachable by zero or more -transitions. We
denote this set by q.
• -closure of a state always contains the state
itself.

41
 Example 2.14
• a*


 a 
1 2 3 4


• 1 = {1, 2, 4}
• 2 = {2}
• 3 = {2, 3, 4}
• 4 = {4}

42
  -Closure of Set of States
•  -closure of a set of states is defined as the union
of  -closures of each individual state.
• If Q = {q1, q2,…qn} is a set of states, then
Q = q 1  q2  …  qn
• In the previous example we had
1 = {1, 2, 4} and 3 = {2, 3, 4}
Let Q = {1, 3}
Q = {1, 3} = 1  3 = {1, 2, 4}  {2, 3, 4} =
{1, 2, 3, 4}

43
 The Subset Construction
• Given NFA M.
• Need to construct a corresponding DFA M’.
1. Compute -closure of the start state of M; this becomes
the start state of M’.
2. For this set and for each subsequent set, we compute
transitions on character a as follows
1. Given a set of states Q and a character a, compute the set of
states Q’a = {t | for some q in Q there is a transition from q to t}
2. Compute Q’a, the -closure of Q’a. This becomes a new state.
There is a transition from Q to Q’a on the character a.
3. Continue with this process until no new states or
transitions are created.
4. Mark as accepting those constructed states that contain
an accepting state of M.
44
 Example 2.15


 a 
1 2 3 4 a

a
1,2,4 2,3,4
• 1 = {1, 2, 4} – start state
• {1, 2, 4}a = {3}
• {3} = {2, 3, 4} – new state and transition
• {2, 3, 4}a = {3}
• {3} = {2, 3, 4} - no new state, new transition

45
 Example 2.16
a  b
 2 3 4 5 
1 8
 a 
6 7

a b
1,2,6 3,4,7,8 5,8

46
 Example 2.17


letter
5 6
letter     
1 2 3 4 9 10

7
digit
8 


letter 4,5,6,7,9,10
letter
letter 2,3,4,5,7,10
1 digit
letter
digit
4,5,7,8,9,10
digit
47
The End
48