Theory of Computation

Lecture#06
Converting NFAs to DFAs

blog.bazaarvoice.com
Umar Faiz
Pakistan Institute of Engineering and Applied Sciences
 DFAS TO NFAS
• NFAs can be constructed from DFAs using  transitions:
• Called NFA-
• Suppose M1 accepts L1, M2 accepts L2
– Then an NFA can be constructed that accepts:
L1 U L2 (union)
L1L2 (concatenation)
L1* (Kleene star)

Slides based on Costas Busch - RPI

 Closure Properties of NFA-


 M1
 M 

M2

(M)*
(M1) U (M2)

  
M1 M2

(M1) (M2)

Slides based on Costas Busch - RPI

 EQUIVALENCE OF MACHINES
• For every nondeterministic automata, there is an equivalent deterministic
automata

• Finite acceptors are equivalent iff they both accept the same language

L(M1) = L(M2)

Slides based on Costas Busch - RPI

 EQUIVALENCE OF MACHINES
• Definition for Automata:
Machine M1 is equivalent to machine M2
if

LM1   LM 2 

Slides based on Costas Busch - RPI

 EQUIVALENCE OF MACHINES
Example of Equivalent Machines
0
LM1   {10} * q0 q1
1 NFA M1

0,1
0
LM 2   {10} * q0 q1 1 q2
1
0 DFA M 2
Slides based on Costas Busch - RPI
 NFAS TO DFAS
• To convert NFAs to DFAs we need to get rid of non-determinism from
NFAs.
• Using subset construction method to convert NFA to DFA involves the
following steps:
– For every state in the NFA, determine all reachable states for every input symbol.
– The set of reachable states constitute a single state in the converted DFA (Each
state in the DFA corresponds to a subset of states in the NFA).
– Find reachable states for each new DFA state, until no more new states can be
found.

Slides based on Costas Busch - RPI

 EQUIVALENCE OF MACHINES


• We will prove:
Languages
Regular
accepted
Languages
by NFAs
Languages
accepted
by DFAs

NFAs and DFAs have the same computation power

Slides based on Costas Busch - RPI
 EQUIVALENCE OF MACHINES
• Step 1


Languages
Regular
accepted
Languages
by NFAs

Proof: Every DFA is trivially an NFA

Any language L accepted by a DFA

is also accepted by an NFA
Slides based on Costas Busch - RPI
 EQUIVALENCE OF MACHINES
• Step 2


Languages
Regular
accepted
Languages
by NFAs
Proof: Any NFA can be converted to an
equivalent DFA

Any language L accepted by an NFA

is also accepted by a DFA
Slides based on Costas Busch - RPI
 CONVERT NFA TO DFA
a
NFA M
q0 a q1  q2
b

DFA M
q0 

Slides based on Costas Busch - RPI

 CONVERT NFA TO DFA

NFA M a
q0 a q1  q2
b

DFA M
q0  a
q1, q2 

Slides based on Costas Busch - RPI

 CONVERT NFA TO DFA
NFA M a
q0 a q1  q2
b
DFA M
q0  a
q1, q2 
b


Slides based on Costas Busch - RPI
 CONVERT NFA TO DFA
NFA M a
q0 a q1  q2
b
a
DFA M
q0  a
q1, q2 
b


Slides based on Costas Busch - RPI
 CONVERT NFA TO DFA
NFA M a
q0 a q1  q2
b
b a
DFA M
q0  a
q1, q2 
b


Slides based on Costas Busch - RPI
 CONVERT NFA TO DFA
NFA M a
q0 a q1  q2
b
b a
DFA M
q0  a
q1, q2 
b

 a, b
Slides based on Costas Busch - RPI
 CONVERT NFA TO DFA
a
NFA M LM   L(M )
q0 a q1  q2
b
a
DFA M b

q0  a
q1, q2 
b

 a, b

Slides based on Costas Busch - RPI

 PROCEDURE FOR CONVERTING NFA TO DFA

We are given an NFA M

We want to convert it to an equivalent DFA M

With

LM   L(M )

Slides based on Costas Busch - RPI

 PROCEDURE FOR CONVERTING NFA TO DFA
If the NFA has states

q0 , q1, q2 ,...

the DFA has states in the powerset

, q0 , q1, q1, q2 , q3 , q4 , q7 ,....

Slides based on Costas Busch - RPI

 PROCEDURE FOR CONVERTING NFA TO DFA

1. Initial state of NFA: q0

Initial state of DFA:

q0 

Slides based on Costas Busch - RPI

 EXAMPLE
NFA M a
q0 a q1  q2
b

DFA M
q0 

Slides based on Costas Busch - RPI

 PROCEDURE NFA TO DFA

2. For every DFA’s state {qi , q j ,...,qm}

Compute in the NFA
 * qi , a ,
 * q j , a ,  {qi , qj ,..., qm
}
...
Add transition to DFA
 {qi , q j ,..., qm }, a   {qi , qj ,..., qm
}
Slides based on Costas Busch - RPI
 EXAMPLE
NFA M a
q0 a q1  q2
b
 * (q0 , a )  {q1, q2 }
DFA M
q0  a
q1, q2 

 q0 , a   q1, q2 
Slides based on Costas Busch - RPI
 PROCEDURE NFA TO DFA

Repeat Step 2 for all letters in alphabet,

until
no more transitions can be added.

Slides based on Costas Busch - RPI

 EXAMPLE
NFA M a
q0 a q1  q2
b
b a
DFA M
q0  a
q1, q2 
b

 a, b

Slides based on Costas Busch - RPI

 PROCEDURE NFA TO DFA

3. For any DFA state {qi , q j ,..., qm }

If some q j is a final state in the NFA

Then, {qi , q j ,..., qm } is a final state in the DFA

Slides based on Costas Busch - RPI

 EXAMPLE
NFA M a
q0 a q1  q2 q1  F
b
a
DFA M  b

q0  a
q1, q2 
b q1, q2  F 
 a, b

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method

3
a
a a b
a b
2
1 a, b 5

a, b 4 a

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
Step1: Construct a transition table showing all reachable states for every state for every
input symbol.
3 Transition from Transition from
a state q with input a state q with input b
a a b q δ(q,a) δ(q,b)
a b
2 1 {1,2,3,4,5} {4,5}

1 a, b 5 2 {3} {5}
3 ∅ {2}
a, b 4 a 4 {5} {4}

* 5 ∅ ∅
b
Slides based on Costas Busch - RPI
 NFA TO DFA
Example1: Subset Construction Method
Step2: The set of states resulting from every transition function constitutes a new state.
Calculate all reachable states for every such state for every input symbol.

q δ(q,a) δ(q,b)
q δ(q,a) δ(q,b) 1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
2 {3} {5}
3 ∅ {2}

4 {5} {4}
5 ∅ ∅

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5}
2 {3} {5}
{4,5}
3 ∅ {2}

4 {5} {4}
5 ∅ ∅

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5}
3 ∅ {2} {2,4,5}
4 {5} {4}
5 ∅ ∅

Slides based on Costas Busch - RPI

 NFA TO DFA
Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5}
4 {5} {4} 5
4
5 ∅ ∅

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5
4
5 ∅ ∅
{3,5}

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4
5 ∅ ∅
{3,5}
∅

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4 5 4
5 ∅ ∅
{3,5}
∅

Slides based on Costas Busch - RPI

NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4 5 4
5 ∅ ∅
{3,5} ∅ 2
∅
{2}
 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4 5 4
5 ∅ ∅
{3,5} ∅ 2
∅ ∅ ∅
{2}

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4 5 4
5 ∅ ∅
{3,5} ∅ 2
∅ ∅ ∅
{2} 3 5
{3}

Slides based on Costas Busch - RPI

 NFA TO DFA
Example1: Subset Construction Method
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5}
1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {2,4,5} {3,5} {4,5}
4 {5} {4} 5 ∅ ∅
4 5 4
5 ∅ ∅
{3,5} ∅ 2
∅ ∅ ∅
2 3 5
3 ∅ 2
Stops here as there are no more reachable states
Slides based on Costas Busch - RPI
 NFA TO DFA
Example1: Subset Construction Method
a
12345 b 245 a
35
a a,b a
b b
1 ∅ a
3
b a,b b
a
a 2
45 5 b
b 4 a

b
Slides based on Costas Busch - RPI
 Single Final State for NFAs

Slides based on Costas Busch - RPI

 • Any NFA can be converted to an equivalent NFA with a single final state

Slides based on Costas Busch - RPI

 EXAMPLE
a

a b
NFA
b

a Equivalent NFA

a b

b 

Slides based on Costas Busch - RPI
 IN GENERAL
NFA

Equivalent NFA

 Single
 final state
Slides based on Costas Busch - RPI
 EXTREME CASE

NFA without final state

Add a final state

Without transitions

Slides based on Costas Busch - RPI

EXAMPLE: -NFA TO DFA CONVERSION
Compute the -Closure of each state. Convert the automaton into DFA.
EXAMPLE: -NFA TO DFA CONVERSION
Compute the -Closure of each state. Convert the automaton into DFA.

EClose(q0) = {q0, q1, q2, q3}

EClose(q1) = {q1, q2, q3}
EClose(q2) = {q2}
EClose(q3) = {q3}
EClose(q4) = {q3, q4}
EXAMPLE: -NFA TO DFA CONVERSION
Compute the -Closure of each state. Convert the automaton into DFA.

a b
{q0, q1, q2, q3} {q0, q1, q2, q3, q4} {q2, q3, q4}
* {q0, q1, q2, q3, q4} {q0, q1, q2, q3, q4} {q2, q3, q4}
* {q2, q3, q4} {q3, q4} {q3, q4}
* {q3, q4} {q3, q4} 
  
EXAMPLE: -NFA TO DFA CONVERSION
Compute the -Closure of each state. Convert the automaton into DFA.

Fully-specified DFA