Epsilon-NFA

Remarks

Example: over $\Sigma = \set{a, b}$, let $Q = \set{0, 1, 2}$, $q_0 = 0$, $F = \set{1, 2}$, $\Delta(0, \varepsilon) = \set{1, 2}$, $\Delta(1, a) = \set{1}$, $\Delta(2, b) = \set{2}$, and $\Delta = \emptyset$ on all other pairs. The word $aa$ is accepted with $y = (\varepsilon, a, a)$ and states $0, 1, 1, 1$, and $L(N) = \set{a^m : m \ge 0} \cup \set{b^n : n \ge 0}$. Non-example: the word $ab$ is not accepted, since after reading $a$ every run is in state $1$, which has no $b$-move. The $\varepsilon$-closure $E(q)$ of a state $q$ is the set of states reachable from $q$ by $\varepsilon$-moves alone. Replacing $\Delta(q, a)$ by $\bigcup_{p \in E(q)} \bigcup_{r \in \Delta(p, a)} E(r)$ and making $q$ accepting when $E(q) \cap F \ne \emptyset$ removes the $\varepsilon$-moves without changing the language.