0
$\begingroup$

I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA.

HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it doesn't have ε transitions, does it mean it is not ε-NFA? If a question asks you to turn a DFA into an ε-NFA, can't you just write the complete DFA as an answer? What properties make DFA different from ε-NFA and NFA?

The same question applies to NFA → ε-NFA, isn't NFA a more "primitive" version of ε-NFA? It's just NFA without the ε...

$\endgroup$
  • $\begingroup$ What is an e-NFA? (I'm guessing an NFA with $\epsilon$ transitions, but I'm not sure) Please detail the model in your question. $\endgroup$ – Shaull Oct 8 '13 at 14:19
  • $\begingroup$ e = epsilon. It's just a food for thought. If example is needed consider a DFA that accepts substring 101 at the end of the string. Making a 4 state DFA. Can this model of DFA also be used as NFA and e-NFA? $\endgroup$ – LarsChung Oct 8 '13 at 14:27
  • $\begingroup$ To elaborate, consider this situation (maybe it can't happen), but here it is: Q1 asks for u to make DFA for end substring 101 (in language 0 and 1). Then WHAT IF Q2 asks you to make this DFA to e-NFA. Would that even be a possibility? $\endgroup$ – LarsChung Oct 8 '13 at 14:31
  • $\begingroup$ Note that these inclusions depend on the exact formal definitions. Different books/lectures use different definitions which lead to different implications. $\endgroup$ – Raphael Oct 9 '13 at 12:54
4
$\begingroup$

If I understand your question correctly, you are essentially talking about the syntactic difference between DFAs, NFAs and NFAs with $\epsilon$ transitions.

Well, in a way, every DFA is also an NFA, and every NFA is also an NFA with $\epsilon$ transitions (it just so happens that the former does not use these transitions). A caveat here is that if you really stick to the standard definitions, then in a DFA the "type" of the transition function returns a state, whereas in an NFA it returns a subset. This is just a technicality, of course, as you can define a DFA to be an NFA whose transition function only returns singletons.

I would look at things this way: An $\epsilon$-NFA would be the "standard". Then, define an NFA to be an $\epsilon$-NFA that does not use the $\epsilon$ transitions. Finally, define a DFA to be an NFA with a single initial state and a transition function that only returns singletons.

In the comments, you ask about the size of the different models, w.r.t a fixed language. This is an entirely different issue. As it turns out, $\epsilon$ transitions can always be removed, and no new states are introduced in the process, only new transitions. As for the translation to DFA - this may involve an exponential blowup in the state space.

$\endgroup$
  • $\begingroup$ So ultimately, you can use a complete DFA for a question that asks for a NFA? Because ultimately they are the same and you can always turn NFA into a DFA through constructive proof $\endgroup$ – LarsChung Oct 8 '13 at 16:45
  • $\begingroup$ If you are asked an NFA and come up with a DFA - great. If you are asked for a DFA and come up with an NFA, then it depends - if you need to explicitly write it down, then you should determinize it. Otherwise, just say that there exists a DFA. Note that its size may be exponential in the size of the NFA. $\endgroup$ – Shaull Oct 8 '13 at 16:50
1
$\begingroup$

Yes, every DFA is an NFA and every NFA is an $\epsilon$-NFA.

Every state in a DFA must have exactly one transition for every symbol in the alphabet. In an NFA, a state can have any number of transitions for each symbol, including zero. But "any number" includes one so anything that meets the definition of a DFA also meets the definition of an NFA. If you like, a DFA is an NFA that happens not to have any nondeterminism.

A state in an $\epsilon$-NFA may have any number of $\epsilon$-transitions to other states. But "any number" includes zero so an NFA (which has no $\epsilon$-transitions from any state) meets the definition of an $\epsilon$-NFA. If you like, an NFA is an $\epsilon$-NFA that happens not to have any $\epsilon$-transitions.

So, yes, if a question asks for an $\epsilon$-NFA, you're within your rights to give a DFA or an NFA: those are just special kinds of $\epsilon$-NFA. On the other hand, if the quesion explicitly asks for an $\epsilon$-NFA, there's probably an $\epsilon$-NFA that's simpler than whatever DFA or NFA you came up with. :-)

$\endgroup$

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.