DFA/NFA/ε-NFA: subsetting each other or different sets?

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 ε...

• 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. – Shaull Oct 8 '13 at 14:19
• 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? – LarsChung Oct 8 '13 at 14:27
• 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? – LarsChung Oct 8 '13 at 14:31
• Note that these inclusions depend on the exact formal definitions. Different books/lectures use different definitions which lead to different implications. – Raphael Oct 9 '13 at 12:54

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.

• 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 – LarsChung Oct 8 '13 at 16:45
• 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. – Shaull Oct 8 '13 at 16:50

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