# Conversion of $\epsilon$-NFA to a DFA

So, I was watching a video about the conversion of $$\epsilon$$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her explanation was that this happens because the state 3 has no outgoing transitions that are labeled with letters from $$\Sigma$$ in the input NFA. See the following image.

So my question is, if the state 3 had an outgoing transition labeled with 0 in the input NFA (see the 2nd image below), then does the state 3 contribute the states 2,4,5, and 6 in the successor set upon reading the letter 0?

• What do you mean by take a state while inputing? Can you explain the question in more detail? – Bader Abu Radi Jan 3 at 9:36
• @BaderAbuRadi I already linked the video at a specific time where she explains this but anyway I'll edit my question to explain in more detail. – Moki Jan 3 at 9:55

What she actually describing is the following construction. For an $$\epsilon$$-NFA $$A = \langle Q, \Sigma, \delta, Q_0, F \rangle$$, the intuitive idea is as follows. Consider a state $$q$$. If there is an $$\epsilon$$-transition from q to $$s$$, then whenever we reach q, we can also reach $$s$$. Yet, there may be $$\epsilon$$-transitions from $$s$$, so we also need to take them into account. For every state $$q\in Q$$, let $$EC(q) \in 2^Q$$ be the $$\epsilon$$-closure of $$q$$ which is formally defined as $$EC(q) = \{s \in Q: \text{ s is reachable from q using only \epsilon-transitions}\}$$. In particular, for every state $$q\in Q$$, $$q\in EC(q)$$ as a state is reachable from itself by a path of length 0.
Now Given the sets $$EC(q)$$ for every state $$q \in Q$$, we define the DFA B as follows. $$B = \langle 2^Q, \Sigma, \kappa, \bigcup\limits_{q\in Q_0} EC(q), \{S\in 2^Q: S\cap F \neq \emptyset\}\rangle$$, where $$\kappa(T, \sigma) = \bigcup\limits_{q\in T} \bigcup\limits_{s\in \delta(q, \sigma)} EC(s)$$, for every set of states $$T\in 2^Q$$, and letter $$\sigma \in \Sigma$$. That is, given a non-$$\epsilon$$ transition $$\langle q, \sigma, s \rangle$$, we move not only to $$s$$, but also to all the states that are reachable from $$s$$ via $$\epsilon$$-transitions.
So indeed, in the first attached image, the state $$3$$ has no outgoing transitions that are labeled with letters from $$\Sigma$$, and thus, for every set $$T$$ that contains state $$3$$, the state $$3$$ does not contribute any states in the set $$\kappa(T, \sigma)$$, for every letter $$\sigma$$. However, in the 2nd attached image, there is a 0-labeled transition going out from the state 3. So, in the DFA $$B$$, when you read the letter 0 from a set $$T$$ that contains the state $$3$$, then the state $$3$$ contributes the states $$\kappa(\{3\}, 0)$$ in $$\kappa(T, 0)$$. Now since $$\delta(3, 0) = \{4\}$$, we have that $$\kappa(\{3\}, 0) = EC(4) = \{2, 4, 5, 6\}$$, that is, you're right that the state $$3$$, upon reading the letter 0, contributes the states $$2, 4, 5,$$ and $$6$$.
Important note: she is doing $$\epsilon$$-transitions removal and the subset construction at the same time. I don't like that at all as it is confusing, also I don't see the formal construction itself in the video. I suggest that you try to do $$\epsilon$$-removal alone (without determinization). That may give you a better understanding as a start.