Finite automata conversion

An important tool in our understanding of finite state automata is in converting from a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA).

Okay problem: NFA states can have multiple edges. We can create a concatenated state that’s the union of any destination states, i.e., for $\{q_0,q_1\}$, we can create $q_{01}=q_0\cup q_1$. Then, any of the original output transitions are also concatenated. If either $q_0$ and/or $q_1$ are accepting states, then the union $q_{01}$ is also an accepting state.

Any missing states in our NFA are assigned the empty set. This is converted to the error state (where all edge transitions are self-loops).

The epsilon-closure (E-closure) of a state $q\in Q$, denoted $\mathcal{E}(q)$, is the set of states that can be reached from $q$ by one or more $ϵ$ transitions, including $q$ itself. The E-closure of a set of states $s\subseteq Q$, denoted $\mathcal{E}(q)$ is the set union of E-closures of members of $s$:

$$\mathcal{E}(s)={\cup }_{m\in s}\mathcal{E}(m)$$

If there are $ϵ$ transitions in the NFA, we instead use the epsilon-closures to encode the states. We follow these steps:

• First, compute the epsilon-closures of the states.
• Create $Q^{\prime }$ as a set with the E-closure states of $q_s$.
• while there are unmarked states in $Q^{\prime }$
  • Select an unmarked state from $Q^{\prime }$ and possibly add to transition table.
  • For each input symbol, compute the E-closure of states that we can transition to from the current state.
  • Add new states that DNE in $Q^{\prime }$ to $Q^{\prime }$. If the states we found in the step above already exist in $Q^{\prime }$, we can skip them.
• Make the accepting states of the NFA accepting states in the DFA.