Conversion of NFA to DFA

•To prove that for every NFA there is a corresponding DFA, we use the
subset construction.
•Note: all we need to do is to find all the components of the new DFA
using the components of the given NFA
•Example:
•Consider the NFA below:

q0 0 q1 1
q2

1
18/09/2025 Richard Ntwari ICS - MUST 1
Conversion of NFA to DFA
The components of the DFA are constructed as follows:
For NFA N = (QN, , N, q0, FN), the goal is to define DFA, D = (QD, , D,
q0, FD), such that L(D) = L(N).
•  is the same as in the NFA,
•q0 is the same as in NFA,
• QD is the set of subsets, S, of QN, where QD is the power set of QN. If
QN has n states, QD will have 2n states. Not all states are accessible from
start state. Inaccessible states can be ‘discarded’.

18/09/2025 Richard Ntwari ICS - MUST 2

Subset Construction
•FD is the set of subsets, S, of QN such that there is at least one final state, i.e., S∩FN
≠
•To compute D, find the union of the states in the set of subsets of QN, such that N
moves from any one of these states, on an input from , to another state i.e, N:

0 1
q0 {q0, q1} {q0}
q1  {q2}
q2  

18/09/2025 Richard Ntwari ICS - MUST 3

Conversion of NFA to DFA
• Since QN = {q0, q1, q2}, from the subset construction, QD = 23 = 8
states including ({q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2})
• To compute D, D (q, a) =  N (p, a)  p in q
• q represents the set of subsets of QN containing atleast one
accepting state of N

18/09/2025 Richard Ntwari ICS - MUST 4

Conversion of NFA to DFA
0 1
  

{q0} {q0, q1} {q0}

{q1}  {q2}

*{q2}  
{q0, q1} {q0, q1} {q0, q2}

*{q0, q2} {q0, q1} {q0}

*{q1, q2}  {q2}
*{q0, q1, q2} {q0, q1} {q0, q2}

18/09/2025 Richard Ntwari ICS - MUST 5

Conversion of e-NFA to DFA
❑Convert to NFA without  by eliminating the -transitions
❑Covert the NFA to DFA using the subset construction
❑That is, from -NFA to NFA to DFA

18/09/2025 Richard Ntwari ICS - MUST 6

MINIMIZATION
• Since we are interested in translating a DFA into a program, we will
want to ensure that this program is as efficient as possible.
• In automata terms, one aspect of this will be to ensure that the
constructed DFA has as few states as possible.
• This is achieved by an algorithm known as DFA minimization.
• We take the “optimistic” approach: we start by assuming that all
states are actually the same, and only distinguish those which we can
prove are different.

18/09/2025 Richard Ntwari ICS - MUST 7

Minimization
• Among many DFAs accepting the same regular language L, there is
exactly one (up to renaming of states) which has the smallest possible
number of states.
• Moreover, it is possible to obtain that minimal DFA for L starting from
any other by the State Minimization Algorithm.

18/09/2025 Richard Ntwari ICS - MUST 8

Deciding Equivalence
• With this algorithm, we can check whether two DFAs A and B
represent the same regular language: just minimize both A and B and
see if the obtained automata are isomorphic (equal up to state
renaming).
• Since we can produce an equivalent DFA for any regular expression or
-NFA, we will know how to recognize whether any two given
representations of regular languages are equivalent.

18/09/2025 Richard Ntwari ICS - MUST 9

Equivalence of States
•Definition:
•Two states p and q of a DFA are
equivalent (notation: p  q) when, for every string w: w leads from p to
a final state if and only if w leads from q to a final state.

18/09/2025 Richard Ntwari ICS - MUST 10

Equivalence of States
• Non-equivalent states are called distinguishable. To show that two
states are distinguishable, we need to find only one string that leads
from one of them to a final state, and leads from the other to a non-
final state.

• The empty string distinguishes every final state from every non-final
state. Thus, if p  q, then p and q are either both final or both non-
final.

18/09/2025 Richard Ntwari ICS - MUST 11

 Equivalence Example
•From the example above, converting our NFA to a DFA:
•Let the new states of the automaton be A for , B for q0, and so on…..
0 1
A A A
B E B
C A D
*D A A
E E F
*F E B
*G A D
*H E F

18/09/2025 Richard Ntwari ICS - MUST 12

Equivalence Example
• Starting from the initial state q0 or B, we can only transition to states E and
F, which is a final state
• From the transition diagram, we see that
▪ D ({q0}, 0) = {q0, q1} and D ({q0}, 1) = {q0}
• {q0} has already been considered but {q0, q1} is new. We also see that, for
the new state {q0, q1}:
▪ D ({q0, q1}, 0) = {q0, q1} and D ({q0, q1}, 1) = {q0, q2}
• Another new state of the DFA is now evident, {q0, q2} or F and:
▪ D ({q0, q2}, 0) = {q0, q1} and D ({q0, q2}, 1) = {q0}
• The results from this calculation are states that we have already seen so no
new states are added to our DFA

18/09/2025 Richard Ntwari ICS - MUST 13

Equivalence Example
• All possible accessible states and their transitions are now evident – the
subset construction has converged
▪ DFA has 3 states, same as the NFA and six transitions compared to the four in the
NFA
• Of the eight original states, only three are accessible from the start state.
The other 5 inaccessible states are ignored.
• Draw the resulting DFA

• Assignment
• Draw the resulting DFA that was obtained from the -NFA in the first
example considered.

18/09/2025 Richard Ntwari ICS - MUST 14

Example 2
0
p q
0
1 1
1
0 r

•Testing two final (or two non-final) states for equivalence is more
difficult. In this example, q and r are equivalent. No string beginning
with 0 can distinguish them: the two paths converge after the first arc.
For strings beginning with 1, the two paths will alternate between q
and r while reading the initial 1's; as soon as the first 0 is read (if ever),
the paths will converge at p.

18/09/2025 Richard Ntwari ICS - MUST 15

Minimal Automata
• Definition: A DFA is minimal iff,

1. All its states are reachable from the start state;

2. All its states are distinguishable.

• Theorem: Two minimal automata for the same language are isomorphic.

• Example:
• The DFA that we obtained from the subset construction above is
minimal.

18/09/2025 Richard Ntwari ICS - MUST 16

Minimal Finite Automata

• Recursive algorithm to find distinguishable states:

• Consider pairs of states {p, q}
• For each pair we will determine whether p is
• distinguishable from q
• Said another way, for each pair {p, q} we will
• determine if p is not equivalent to q.

18/09/2025 Richard Ntwari ICS - MUST 17

Minimal Finite Automata
• Recursive algorithm
• Base case:
• If p is accepting and q is non-accepting then {p, q} is distinguishable
• Induction
• For some pair {p, q}, if
• –  (p, a) = r and  (q ,a) = s and {r, s} is distinguishable then {p, q} is
distinguishable

18/09/2025 Richard Ntwari ICS - MUST 18

Minimization Strategy
• Assume we’re given a DFA D = (Q, , , q0, F) for L. The minimization
process consists of two steps:
[Link] rid of inaccessible states, i.e. all states q for which there exists no
word w  * such that
• (q0, w) = q.
[Link] equivalent states.
• The next slide provides an algorithm for computing the collapsing relation
 for a given DFA D with no inaccessible states. The algorithm will mark
pairs of states {p, q}.
• A pair will be marked as soon as a reason is discovered why p and q are
not equivalent.

18/09/2025 Richard Ntwari ICS - MUST 19

Minimization Algorithm
1. Write down a table of all pairs of states {p, q}, initially unmarked.
2. Mark {p, q} if p  F and q  F or vice versa.
3. Repeat the following until no more changes occur:
• If there exists an unmarked pair {p, q} such that { (p, a),  (q,
a)} is marked for some a  ,
Then mark {p, q}.
4. When done, p  q  {p, q} is not marked.

18/09/2025 Richard Ntwari ICS - MUST 20

Example
0, 1

0
q1 q2
1
0 0, 1

q0 q4

1 1 0, 1

0
q5 q6

18/09/2025 Richard Ntwari ICS - MUST 21

Example
Step 1:

Initially, all pairs are unmarked in the table.

0
- 1
- - 2
- - - 4
- - - - 5
- - - - - 6

18/09/2025 Richard Ntwari ICS - MUST 22

Example Cont’d
0
• Step 2: - 1
  2
- -  4
- -  - 5
  -   6

After step 2, all pairs consisting of one accept state and one non-accept state
have been marked.

18/09/2025 Richard Ntwari ICS - MUST 23

Example Cont’d
• Step 3:
• Iteration 1:
• Now look at an unmarked pair, say {q0, q1}. Under input 0, {q0, q1} go
to {q1, q2}, respectively. The pair {q1,q2} is already marked, so we mark
{q0,q1).
• Similarly, {q0, q5} goes over 0 to {q1, q6} and therefore gets marked,
and so do {q4, q5} and {q1, q4}.
• {q0, q4} goes over 0 to {q1, q4} which is not marked, so we don’t mark
{q0, q4}, at least not yet. Over 1 it goes to {q5, q4}, so it remains
unmarked.

18/09/2025 Richard Ntwari ICS - MUST 24

 Example Cont’d
0 •Giving:
 1

  2

-   4

 -   5

  -   6

18/09/2025 Richard Ntwari ICS - MUST 25

• Step 3:
• Iteration 2:
• If we now reconsider {q0, q4}, we notice that {q0, q4} goes over 0 to {q1, q4},
which by now is already marked. We therefore mark {q0, q4} as well.
• {q1, q5} and {q2, q6} remain unmarked. 0
 1
  2
   4
 -   5
  -   6
18/09/2025 Richard Ntwari ICS - MUST 26
Example
• Step 3:
• Iteration 3:
• Since no more changes occur during this iteration (i.e. no new pair
gets marked), we quit step 3.

• Step 4:
• We’re left with unmarked pairs {q1, q5} and {q2, q6}, indicating that q1
 q5 and q2  q6.

18/09/2025 Richard Ntwari ICS - MUST 27

Resulting automaton

• q1 has been combined with q5 and q2 with q6. You can also choose to
combine and keep q2 and q5 instead
q1
1
0, 1 0,1

q0 q4
0
0,1

q6

18/09/2025 Richard Ntwari ICS - MUST 28

Exercise
Find the minimal automaton equivalent to the following by:
a) Identifying the equivalent states using the state minimization algorithm
b) Draw the resulting automaton with the equivalent states combined

a b
1 a 2 b 3 a 4
a b
b
a b
b b a
5 6 7 8
b a
a
18/09/2025 Richard Ntwari ICS - MUST 29
End
• Questions???

18/09/2025 Richard Ntwari ICS - MUST 30