When converting a epsilon NFA to NFA to DFA, how to handle the start state?

Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3

We know when converting from epsilon NFA to NFA, we apply the following formula for each state: E(T(E(state), input)), where E = epsilon closure and T = transition function. In this stage the start state for the NFA remains the same as it was for epsilon NFA, right?

Now, when we convert the NFA to DFA, are we still supposed to use the same start state that was in the NFA and epsilon NFA because if you think about this then when directly converting from epsilon NFA to NFA we use epsilon-closure of the start state. So, remembering the first line of the post

• In the above case: If we use the same start state we would end up with a single set element representing the start state ( same as that of NFA and eNFA ) in this case it would stay "1"

• If we directly convert eNFA to NFA then the start state would be "1,3"

This might seem minute, but it changes the entire language in the final DFA

There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. Consider $(Q, \Delta, I, F)$ an $\varepsilon$-NFA.

• In the forward closure, you are trying to apply $\varepsilon$-transitions after each normal transition, to see where you can reach. Since that is the case, you must just be sure that there is no problem for the very first transition, and modify the starting states. A NFA recognizing the same language would be $(Q, \Delta', I', F)$, where $I'=\mathcal{E}(I)$ and $\Delta'(q, a) = \mathcal{E}(\Delta(q, a))$.

• In the backward closure, you are trying to apply $\varepsilon$-transitions before each normal transition, to see from where you can start. Since that is the case, you must consider the very last transition, and modify a bit final states. A NFA recognizing the same language would be $(Q, \Delta'', I, F'')$, where $F'' = \{q\in Q\mid \mathcal{E}(q) \cap F \neq \emptyset\}$ and $\Delta''(q, a) = \bigcup\limits_{p\in \mathcal{E}(q)}\Delta(p, a)$.

Of course, if your convention of NFA allows only one starting state, only the second transformation can be applied, unless $I = \{q_0\}$ and $\mathcal{E}(q_0) = \{q_0\}$.

Here are some example of conversions. Despite being different, all those NFA's recognize the language $a^b^c^*$.

The idea for converting $\varepsilon$-NFA directly to DFA is exactly the same: you either apply $\varepsilon$-closure after transitions, but start from a bigger set of states, or apply before transitions and modify final states.

In the previous example, the backward closure is already a DFA (but it is not always the case).

StackExchange Computer Science Q#156437, answer score: 5