NFA to DFA Conversion (Determinisation)

COMP218 Lectures 2021-10-04

An ($\epsilon$-)NFA can do everything a DFA can do and vice-versa.

Every ($\epsilon$-)NFA can be converted into a DFA for the same language.

Method

1. Eliminate $\epsilon$-transitions ($\epsilon$-NFA to NFA).
2. Convert NFA to DFA.

NFA to DFA (Intuition)

To do this you split out the possible states into sets of states. The sets of states containing the accepted state become the new accepted states.

• NFA

    stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0:0,1
    q0 --> q1:1
    q1 --> q2:0
    q2:q2
  

• DFA

    stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0:0
    q0 --> [q0,q1}:1
    [q0,q1} --> [q0,q1}: 1
    [q0,q1} --> q2:0
    q2: {q0, q2}
    q2 --> [q0,q1}:1
    q2 --> q0:0
  

This explores the powerset of states. We can then graph all transitions and prune states that are unreachable.

General Method

	NFA	DFA
States	$q_0,q_1,\ldots,q_n$	$\emptyset,\{q0\},\{q1\},\{q_0,q_1\},\ldots,\{q0,\ldots,q_n\}$ (one for each subset of states in the NFA)
Initial State	$q_0$	$\{q_0\}$
Transitions	$\delta$	$\delta’(\{q_{i1},\ldots,q_{ik}\},a)=$ $\delta(q_{i1},a)\cup,\ldots,\cup\delta(q_{ik},a)$
Accepting States	$F\subseteq Q$	$F’=\{S:S\text{ contains some state in } F\}$

This technique is called the subset construction and is also used in AI.

This technique always produces a DFA of size $2^n$ where $n$ is the number of states in the related NFA. Hence, the intuitive method is preferred.

Additional Example

• NFA

    stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0:1
    q0 --> q1:0
    q0 --> q2:0
    q1 --> q1:1
    q1 --> q2:0,1
    q2 --> q2:0
    q1:q1
    q2:q2
  

• DFA

    stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0:1
    q0 --> q12:0
    q12 --> q12:1
    q12 --> q2:0
    q2: q2
    q2 --> q2:0
    q2 --> emptyset:1
    emptyset --> emptyset:0, 1
    q12: {q1, q2}