0
$\begingroup$

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:enter image description here

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: enter image description here

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

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

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.

$\endgroup$
  • $\begingroup$ Can you help me at this case? I try to follow your algorithm, bum I's still confuse... :( (but thank you anyway!!) $\endgroup$ – stud1 Nov 19 '15 at 19:22
  • $\begingroup$ 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?? $\endgroup$ – stud1 Nov 19 '15 at 20:06
  • $\begingroup$ @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. $\endgroup$ – G. Bach Nov 19 '15 at 21:21
  • $\begingroup$ @G.Bach - I think I did it... I post it as answer... (Hope it's OK). Did I right? $\endgroup$ – stud1 Nov 19 '15 at 21:37
0
$\begingroup$

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: enter image description here

Thank you!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 20 '15 at 8:24
  • $\begingroup$ 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...) $\endgroup$ – stud1 Nov 20 '15 at 9:49
  • $\begingroup$ See templatetypdef's answer. $\endgroup$ – Raphael Nov 20 '15 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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