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

Problem Detail: 

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

Asked By : LarsChung

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14908