3
$\begingroup$

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

  1. 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"
  2. 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

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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^*$.

enter image description here

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).

$\endgroup$
12
  • $\begingroup$ This is great!, i have a small doubt, some people do epsilon closure twice once before reading the input and once after, example: youtube.com/watch?v=WSGcmaHNBFM&t=495s .Now, if you think about it with each of these methods: 2 methods that you mentioned and this method from youtube, all of them would produce different NFAs and hence different languages, so which one is correct? $\endgroup$ Commented Dec 27, 2022 at 5:56
  • 2
    $\begingroup$ Different NFA does not mean different languages. It is correct to apply the $\varepsilon$-closure twice, but you could say it is "overkill" and unecessary. I added some example to see that even though the resulting automata are different, they recognize the same language. $\endgroup$
    – Nathaniel
    Commented Dec 27, 2022 at 13:22
  • 2
    $\begingroup$ The examples are great! $\endgroup$ Commented Dec 27, 2022 at 20:24
  • $\begingroup$ Thanks for the comment! $\endgroup$
    – Nathaniel
    Commented Dec 27, 2022 at 20:30
  • $\begingroup$ @Nathaniel The diagrams solved the problem for me! Thank you. One final question, we can see that in forward closure and full closure there are multiple start states, my convention of NFA / DFA allows only 1 start state, so is it possible to combine the multiple start states to one start state in forward closure and full closure but my guess is that then the epsilon NFA would be automatically converted to a DFA. Am i right? $\endgroup$ Commented Dec 28, 2022 at 5:53

Your Answer

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

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