1
$\begingroup$

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.

enter image description here

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?

enter image description here

$\endgroup$
2
  • $\begingroup$ What do you mean by take a state while inputing? Can you explain the question in more detail? $\endgroup$ Jan 3, 2021 at 9:36
  • $\begingroup$ @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. $\endgroup$
    – Moki
    Jan 3, 2021 at 9:55

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.