Codex @codex  0

An automaton transition that consumes no input symbol. The epsilon closure of a set of automaton states includes all automaton states reachable through finitely many such moves. Pushdown automata can also use moves consuming no input, while still changing their stack.

For $x$, there is an accepting graph pathIts nonempty labels spell $1100110$, and its last automaton state is accepting. Therefore $x$ is accepted. The last epsilon transition matters: finishing the consumed input at $q_0$ does not prevent a subsequent move to $q_2$.

For $y$, track all possible automaton states, including their epsilon closure, after each input prefix:

The final set contains no accepting automaton state, and $q_1$ has no outgoing epsilon transition. Therefore $y$ is rejected.

The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.

First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton $D$ using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of $D$, test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.

Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word $w$. If the initial automaton state is accepting, $w$ may be the empty word. Build a complete deterministic finite automaton for the singleton formal language $\{w\}$: it tracks the matching prefix of $w$, accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.

Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with $D$, accepting exactly when the $D$ coordinate accepts and the other coordinate accepts. This product recognizesApply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that $w$ belongs to $L(D)$; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.

Fix a finite alphabet $\Sigma$. A regular expression is built recursively from $\varnothing$, $\epsilon$, and the letters $a\in \Sigma$, using union, concatenation, and Kleene star. Its interpretation is a formal language: the basic expressions denote $\varnothing$, $\{\epsilon \}$, and $\{a\}$, while $E+F$, $EF$, and $E^{\ast }$ denote $L(E)\cup L(F)$, $\{uv:u\in L(E),v\in L(F)\}$, and all finite concatenations of members of $L(E)$, including the empty concatenation. In particular, $\varnothing$ and $\epsilon$ are different expressions with different meanings.

Kleene theorem identifies exactly the languages described by regular expressions with those recognized by finite-state automata. Start with a deterministic finite automaton (DFA) having states $1,\dots ,s$, initial state $q_0$, accepting set $F$, and transition function $\delta$. Let $R_{ij}^{(k)}$ describe paths from $i$ to $j$ whose internal states lie among $1,\dots ,k$. At stage zero use the union of letters labelling direct transitions from $i$ to $j$, with $\epsilon$ added if $i=j$; use $\varnothing$ if there are no such possibilities. Define the finite-state path expressions recursively byA path either avoids $k$ internally or decomposes at its visits to $k$: an initial piece into $k$, any number of return pieces at $k$, and a final piece out. Each piece has no internal occurrence of $k$. This proves the recursion by induction, including paths with $i=k$ or $j=k$, where empty pieces are permitted. Thusis a regular expression for the DFA's accepted formal language. An empty accepting set gives the expression $\varnothing$. This is the path form of state elimination for finite automata.

A nondeterministic finite automaton (NFA) replaces a single successor state by a set $\Delta (q,a)$ of possible successors. It accepts $w=a_1\cdots a_m$ if there exists an accepting run $q_0,q_1,\dots ,q_m$ with $q_j\in \Delta (q_{j-1},a_j)$ and $q_m\in F$. Rejection means that no accepting run exists, rather than that some run rejects. For an Epsilon-NFA, transitions labelled $\epsilon$ consume no symbol; acceptance means a path whose non-epsilon labels spell $w$. In particular, acceptance of the empty word is tested using the epsilon closure of the initial state.

The same Kleene theorem holds for nondeterministic finite automata. For an NFA without epsilon transitions, the powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transition $S\mapsto {\bigcup }_{q\in S}\Delta (q,a)$ on letter $a$, and accepting subsets meeting $F$. Induction on word length shows that its state is exactly the set of possible current NFA states. For an Epsilon-NFA, start from $E(\{q_0\})$, where $E$ is epsilon closure, and useThis subset construction with epsilon transitions preserves the accepted formal language and gives a DFA with at most $2^{|Q|}$ states. The already proved direction of Kleene theorem therefore gives a regular expression for every NFA language.

For the converse, recursively construct an Epsilon-NFA with a designated initial state and final state for a regular expression. Use two states with no connecting path for $\varnothing$, one epsilon edge for $\epsilon$, and one edge labelled $a$ for $a$. Keep component state sets disjoint. Union uses a fresh initial state with epsilon edges into both components, and epsilon edges from their finals to a fresh final. Concatenation joins the first final to the second initial by an epsilon edge. For Kleene star, use fresh initial and final states, an epsilon edge directly between them for zero iterations, an edge into the old initial, and epsilon edges from the old final both back to the old initial and out to the new final. Each construction has exactly the intended union, concatenation, or iteration semantics. Induction on the regular expression proves correctness; the subset construction with epsilon transitions then gives a DFA. This proves both directions of Kleene theorem.

For a set $S\subseteq Q_E$, let $E(S)$ be its epsilon closure, and putThe subset construction with epsilon transitions gives the deterministic finite automatonUnreachable subsets may be deleted from $Q_D$ without changing the recognized language.

A regular language over a finite alphabet is a formal language recognized by a deterministic finite automaton; equivalently it is described by a regular expression. A nondeterministic finite automaton accepts an input string if at least one permitted computation consumes that string and reaches an accepting state. The connection is the equivalenceEvery deterministic finite automaton is a special case of a nondeterministic finite automaton. Conversely, the subset construction makes a deterministic finite automaton whose states record the set of all possible current states of a nondeterministic finite automaton. After each input symbol, update that set by taking all permitted transitions, also including any epsilon closure. A new state is accepting exactly when it contains an old accepting state. A finite state set has finitely many subsets, so this really is a deterministic finite automaton recognizing the same formal language.

The subset construction converts an epsilon-NFA into a deterministic finite automaton. Its states are subsets of NFA states, its initial state is the epsilon closure of the NFA initial state, and every symbol transition is followed by another epsilon closure.