1
$\begingroup$

If for every $\epsilon$-NFA their exists an equivalent NFA what is the purpose of ever using an $\epsilon$-NFA? I am having trouble understanding what the practical purpose of using one would be.

$\endgroup$
  • 1
    $\begingroup$ compgroups.net/comp.compilers/… $\endgroup$ – Aditya Jun 21 '17 at 3:11
  • $\begingroup$ What is the practical purpose of Java and Haskell? After all, Turing machines and lambda calculus are just as powerful, so why do we need these very complicated languages? $\endgroup$ – Raphael Jun 21 '17 at 4:42
  • $\begingroup$ Well said Sir.. $\endgroup$ – Aditya Jun 21 '17 at 15:13
2
$\begingroup$

Purely convenience. It's like, in a programming language, why have for loops, if every for loop could alternatively be written as a while loop? Convenience. It's sometimes convenient to be able to use epsilon-transitions, when defining NFAs. For instance, when converting a regexp to a NFA, the construction is arguably a bit simpler (easier to understand) if you allow yourself to use epsilon-transitions.

$\endgroup$
1
$\begingroup$

Given a regular expression constructing an equivalent NFA with epsilon is easier than constructing equivalent DFA. Also given two DFAs you can easily construct NFAs with epsilon moves accept concatenation, intersection, union, and Kleene closure of the languages. Look here for example.

$\endgroup$
  • $\begingroup$ NFAs without epsilon are only slightly less convenient for these constructions than those with, and cause fewer inconveniences elsewhere. $\endgroup$ – Raphael Jun 21 '17 at 6:17
  • $\begingroup$ @Raphael, try to construct an NFA without epsilon move for the following reg exp and feel the real convenience of using NFA with epsilon moves: $(a^*ab + b^*ab(ab +c)^*)^*$ $\endgroup$ – fade2black Jun 21 '17 at 7:45
  • $\begingroup$ Done it before; just change the standard construction to do the epsilon-closure directly. Not nice, but not too bad either. I encountered that variant in the context of proving that some logic was as powerful as NFA; that construction would have been very awkward had the FA been allowed to have epsilon-transitions. (Not that there had not been other ways around this, but I never claimed that there weren't.) Anyway, the point is: comparing epsilon-NFA with DFA is only half the story; you need to include non-epsilon-NFA in the comparison. $\endgroup$ – Raphael Jun 21 '17 at 8:07

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.