Acceptance of a word by an NFA and the recognized language

Let $N=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ be an NFA with epsilon-moves as in Nondeterministic finite automata with epsilon-moves. For $S\subseteq Q$ and $w\in {\mathrm{\Sigma }}^{\ast }$, define $\widehat{\delta }(S,w)$ to be the set of states $r_m$ for which there are a finite state list $r_0,\dots ,r_m$ and labels $a_1,\dots ,a_m\in \mathrm{\Sigma }\cup \{\epsilon \}$ such that $r_0\in S$, $r_i\in \delta (r_{i-1},a_i)$ for $1\le i\le m$, and deleting every $\epsilon$ label from the label list gives exactly $w$. The case $m=0$ is allowed and reads the empty word. Put $\widehat{\delta }(q,w)=\widehat{\delta }(\{q\},w)$ for a state $q$.

This is a well-defined subset of the finite state set $Q$. Writing $E(S)=\widehat{\delta }(S,\epsilon )$, it satisfies $\widehat{\delta }(S,wa)=E\text{\hspace{0.17em}⁣}({\bigcup }_{q\in \widehat{\delta }(S,w)}\delta (q,a))(a\in \mathrm{\Sigma })\mathrm{.}$ Indeed, split a run immediately before and after its last non-epsilon move: its prefix reads $w$, that move reads $a$, and its suffix uses only epsilon moves. Conversely concatenating these three finite pieces constructs a run reading $wa$. Thus the finite-run definition also supplies the usual recursively extended transition, including epsilon moves before and after the input.

A word $w\in {\mathrm{\Sigma }}^{\ast }$ is accepted by $N$ when $\widehat{\delta }(q_0,w)\cap F\mathrm{\ne }\mathrm{\varnothing }\mathrm{.}$

The language recognized by $N$ is $L(N):=\{w\in {\mathrm{\Sigma }}^{\ast }:\widehat{\delta }(q_0,w)\cap F\mathrm{\ne }\mathrm{\varnothing }\}\mathrm{.}$ This is a language over $\mathrm{\Sigma }$ in the sense of Languages over an alphabet.

• NFA acceptance is existential: one accepting computation path is enough.

• Rejection means that no computation path ends in an accepting state after the whole input has been read.