Nondeterministic finite automata with epsilon-moves

Let $\mathrm{\Sigma }$ be an alphabet. A nondeterministic finite automaton with epsilon-moves is a quintuple $N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ such that:

• $Q$ is a finite set of states.
• $q_0\in Q$ is the start state.
• $F\subseteq Q$ is the set of accepting states.
• $\delta$ assigns to each pair $(q,x)\in Q\times (\mathrm{\Sigma }\cup \{\epsilon \})$ a subset $\delta (q,x)\subseteq Q$, equivalently an element of $\mathcal{P}(Q)$ in the sense of The power set $\mathcal{P}(x)=\{z:z\subseteq x\}$.

Thus a letter $a\in \mathrm{\Sigma }$ may lead from one state to several next states, and an $\epsilon$-transition changes state without consuming an input symbol.

• A DFA in the sense of Deterministic finite automata is the special case in which every set $\delta (q,a)$ is a singleton and every $\delta (q,\epsilon )$ is empty.

• The symbol $\epsilon$ is not an extra alphabet letter. It records a move that reads nothing.