Difference between a deterministic and a nondeterministic finite automaton

Question

I am currently working on the automata theory and just passed through the definition of a nondeterministic and a deterministic finite automaton. The definition are quite similar and I don't understand well the difference between them. Can someone maybe passe again through them and also underline the difference with an example, if it is possible? Many thanks!

Answer 1

Both automata start from a single starting state. A deterministic automaton, if it is in some state $q$ and it reads an input character, it will transit to a single state $q'$. A non-deterministic automaton can transit from a state $q$ to many states $q_1, q_2, \ldots, q_k$ at the same time by reading a single input character. Also, a non-deterministic automaton can transit from one state to another even without reading input (these are $\varepsilon$-transitions). Intuitively, the non-deterministic automaton can make several transitions in parallel (and you have to take into account all of them), while the deterministic one has only one way to move at every step.

This difference is encoded in the signature of the transition functions for DFAs and NFAs. If $Q$ is the set of states and $\Gamma$ the set of characters, then the transition functions have the following signatures: $$\delta_{D}: Q\times\Gamma \to Q\quad\quad\quad\quad\quad \delta_N:Q\times(\Gamma\cup\{\varepsilon\})\to \mathcal{P}(Q)$$ where $\delta_D$ is the transition function of a DFA and $\delta_N$ of an NFA. The signature on the left means that from a single state and by reading a single input character, the automaton transits to a single state. The signature on the right means that from a single state and by reading a single input character or by reading no character at all, the automaton can transit to a set of states.