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

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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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!

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 at 9:49
  • $\begingroup$ See templatetypdef's answer. $\endgroup$
    – Raphael ♦
    Nov 20, 2015 at 12:15

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.