Difference between NFA and DFA

In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.

Each input to a DFA or NFA affects the state of the automaton: if it was in state $q$ immediately before the input, either it will be in some state $q'$ after the input, or the input will cause it to choke. (Note that $q'$ may be the same as $q$.) Suppose that we have an automaton in a state $q$. The difference in behavior between a DFA and an NFA is this:

• If it’s a DFA, each possible input determines the resulting state $q'$ uniquely. Every input causes a state change, and the new state is completely determined by the input. Moreover, the automaton can change state only after reading an input.

• If it’s an NFA, some inputs may allow a choice of resulting states, and some may cause the automaton to choke, because there is no new state corresponding to that input. Moreover, the automaton may be constructed so that it can change state to some new state $q'$ without reading any input at all.

As a consequence of this difference in behavior, DFA’s and NFA’s differ in another very important respect.

• If you start a DFA in its initial state and input some word $w$, the state $q$ in which the DFA ends up is completely determined by $w$: inputting $w$ to the DFA will always cause it to end up in state $q$. This is what is meant by calling it deterministic.

• If you start an NFA in its initial state and input some word $w$, there may be several possible states in which it can end up, since some of the inputs along the way may have allowed a choice of state changes. Consequently, you can’t predict from $w$ alone in exactly which state the automaton will finish; this is what is meant by calling it nondeterministic. (And it’s actually a little worse than I’ve indicated, since an NFA is also allowed to have more than one initial state.)

Finally, these differences affect how we determine what words are accepted (or recognized) by an automaton.

• If it’s a DFA, we know that each word completely determines the final state of the automaton, and we say that the word is accepted if that state is an acceptor state.

• If it’s an NFA, there might be several possible final states that could result from reading a given word; as long as at least one of them is an acceptor state, we say that the automaton accepts the word.

What I’ve described informally is the view of an NFA that makes it look most like a DFA and that I think best explains why it’s called nondeterministic. There is, however, another way of looking at NFAs: it’s also possible to think of an NFA as being in multiple states at once, as if it were making all possible choices at each input. If you think of it in those terms, you can say that it accepts a word provided that at least one of the states in which it ends up after reading that word is an acceptor state. This point of view is perhaps most useful for understanding the algorithm used to turn an NFA into an equivalent DFA.

Automata are abstract machines that have a finite set of states. Given some input, they transition from state to state. You can think of them sort of like flowcharts.

An NFA is a Nondeterministic Finite Automaton. Nondeterministic means it can transition to, and be in, multiple states at once (i.e. for some given input).

A DFA is a Deterministic Finite Automaton. Deterministic means that it can only be in, and transition to, one state at a time (i.e. for some given input).

The major important difference is that an NFA is usually much more efficient.