An NFA can always be simulated by a DFA, with potentially many more but still a finite number of states.

<aside> 💡 We can use the idea that an NFA’s state information can be captured precisely by subsets of its set of states to build our DFA.

</aside>

This is known as subset construction.

Example

So we write out a new node in our DFA, each corresponding to the set of states that we could end up in in our NFA at any given time. It is then rather trivial to draw our transitions between these states.

The empty set corresponds to when the NFA ‘breaks’, ie. when there is no transition from the state we are in for the given letter. We make this state a dead state (all letters transition back into it).

<aside> ➖ Since the states labelled $\{q_0\}$ and $\emptyset$ are unreachable from the other states, from where we start, we can simply remove them from our DFA.

</aside>

Formalised 👔

A general description can be given for deriving a DFA from a given NFA.

Let $N = (Q, \sum, q_0, F, \delta)$ be the NFA

and $M=(Q_1, \sum, q_1, F_1, \delta_1)$ the DFA.

• $Q_1 = 2^Q$
  • That is, the set of states in $M$ will be ‘labelled’ with the powerset of $N$ ’s states
• $q_1 = \epsilon CLOSE(q_0)$
  • That is, the start node of $M$ should be ‘labelled’ as the set of all possible start states in $N$
• $F_1 = \{X \subseteq Q :X\cap F \neq \emptyset\}$
  • That is, the finishing states of $M$ should be all nodes ‘labelled’ with subsets of $Q$ such that they have at least one finishing state in them.
  • This corresponds to saying there is at least one copy of the NFA which would end up in a final state for the word, and that is what we need for it to be accepted.
• $\delta_1(X, a) = \bigcup_{x\in X} \epsilon CLOSE(\delta(x, a))$
  • ie. For the node you are on, labelled with the set of states $X$, move to the node labelled with all the states you can reach from each $x \in X$ after reading $a$ and then taking all $\epsilon$ transitions