= Solution
A <nondeterministic finite automaton>, allowing the <epsilon transitions> used in this paper, is a <tuple>
$$
M=(Q,\Sigma,\delta,q_0,F),\qquad
\delta:Q\times(\Sigma\cup\{\varepsilon\})\longrightarrow\mathcal P(Q).
$$
Here $Q$ is a nonempty <finite set> of <automaton states>, $\Sigma$ is a finite <alphabet>, $\mathcal P(Q)$ is the <power set> of $Q$, $q_0\in Q$ is the initial <automaton state>, and $F\subseteq Q$ is the <set> of accepting <automaton states>. The symbol $\varepsilon\notin\Sigma$ denotes the <empty word>. Membership $r\in\delta(q,a)$ permits an <automaton transition> from $q$ to $r$ consuming $a$ when $a\in\Sigma$, or consuming nothing when $a=\varepsilon$.
The recognized <formal language> is
$$
\boxed{L(M)=\{w\in\Sigma^*: \text{some finite path from }q_0\text{ to a state in }F\text{ has label }w\}.}
$$
The label of a <graph path> is the <concatenation> of its labels with all occurrences of $\varepsilon$ omitted. Thus acceptance requires consuming the entire input <word>; a single successful choice of <automaton transitions> suffices. A path of length zero is allowed, so the <empty word> is accepted whenever $q_0\in F$, or an accepting <automaton state> is reachable by <epsilon transitions>. If <epsilon transitions> are excluded from the definition of a <nondeterministic finite automaton>, the displayed version is called an <Epsilon-NFA>.
Back to article page
