# How to make a NFA (or DFA) from $\varepsilon$NFA?

I need to build a DFA from $$\varepsilon$$NFA, so first of all I assume that I need to convert the $$\varepsilon$$NFA to NFA and then to DFA (because I know the method of converting from NFA to DFA, and we learn how to remove $$\varepsilon$$'s from $$\varepsilon$$NFA and make it NFA.
But the I'm still stuck at some cases....

For example:
See this $$\varepsilon$$NFA:

I want to make it NFA (I don't know if to write the whole algorithm...), and I'm not sure which is right:

This:

Or this (at the comments.... I can't put more then 2 images)

I think that the first is the right one, but I'm not sure...
At the second one - the number of the 0-s must be even to be at $$q_1$$ but at the original $$\varepsilon$$NFA it can be any number of 0-s...

One more thing, it's correct that I'm not putting 0,1 insted of the $$\varepsilon$$? (Because 1 from $$q_0$$ brings me to $$\varnothing$$...)

• Here is the other NFA: i.stack.imgur.com/VS9Pa.jpg Nov 19 '15 at 18:14
• Hint: $\varepsilon$-closure.
– Raphael
Nov 19 '15 at 20:30
• @Raphael, I use it at my answer! Thank you! Nov 19 '15 at 22:06

I think the following should work. For each state q, define E(q) to be the set of all states reachable from q by following zero or more ε-transitions. Then, create a new NFA as follows:

• The set of states in the NFA is the set $\{ E(q) | q \in Q \}$.
• The start state is $E(q_0)$.
• For each state $E(q)$ in the new NFA, the transitions are given as follows: for each state $r \in E(q)$ that has a transition to a state $s$ on a character $a$, add a transition from $E(q)$ to $E(s)$ on $a$.
• The accepting states in the NFA are the states containing at least one accepting state in the original NFA.

The basic idea behind the construction is to have each NFA state correspond to a set of states in the ε-NFA. This effectively simulates taking all possible ε-transitions at each point in time.

• Can you help me at this case? I try to follow your algorithm, bum I's still confuse... :( (but thank you anyway!!) Nov 19 '15 at 19:22
• Can you explain more about $E(q)$? At the 3rd point - what do you mean when you wrote: $E(q)$ to $E(s)$?? It's set of states, no?? Nov 19 '15 at 20:06
• @stud1 $E(q)$ is the set of all states reachable from $q$ via $\epsilon$-transitions. In your new $\epsilon$-free NFA, the sets $E(q)$ become your new states, and then you'll want to figure out which transitions they need. To do that, you have to figure out all walks in the original $\epsilon$-NFA that contain exactly one non-$\epsilon$. To find a walk starting from $q$ that contains exactly one non-$\epsilon$-transition, look at some $r \in E(q)$, pick any transition from $r$ to $s$ with symbol $a$ in the original $\epsilon$-NFA, and add a transition $\delta(E(q),a) = E(s)$ to your new NFA. Nov 19 '15 at 21:21
• @G.Bach - I think I did it... I post it as answer... (Hope it's OK). Did I right? Nov 19 '15 at 21:37

I think I know the answer, I try few times, then I look at the definition of ε-closure and how to make NFA from εNFA, and I think I got the answer -

First of all I followed the definition: $\delta '(q,a) = E(\delta(q,a))$ [$\delta'$ is the $\delta$ function of the new NFA].

Now:

• $\delta'(q_0,0)=E(\delta(q_0,0))=E(\{q_1\})=\{q_0,q_1\}$.
• $\delta'(q_1,0)=E(\delta(q_1,0))=E(\varnothing)=\varnothing$.
• $\delta'(q_1,1)=E(\delta(q_1,1))=E(\varnothing)=\varnothing$.

So the first option that I put was right....

Here:

Thank you!

• Hm, the resulting automaton seems correct but I'm not sure you did the correction in the right way. The way I know it, you get new states, starting with $\{q_0\}$ (the starting state). That means you then have a state $\{q_0, q_1\}$ for which you have to determine the $\varepsilon$-closure.
– Raphael
Nov 20 '15 at 8:24
• What do you mean? I don't understand... i.e. where I'm wrong? I try to make here a NFA (the DFA it's at the next step...) Nov 20 '15 at 9:49