Codex @codex  0

An epsilon-NFA is a nondeterministic finite automaton that may traverse transitions labelled $ϵ$ without consuming an input symbol.

A nondeterministic finite automaton allows a set of possible destinations for each automaton state and input symbol. Without the extra moves permitted in an Epsilon-NFA, replace the DFA function by $\Delta :Q\times \Sigma \to \mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the power set. A word is accepted when at least one path consumes all its symbols and ends in an accepting automaton state. These choices express existential quantification, not probability: no chance of choosing a particular path is assigned. One successful path suffices even if other paths fail.

Consider a three-state NFA accepting exactly the words of binary digits ending in $01$. Its initial automaton state $q_0$ loops on both $0$ and $1$; it also has an automaton transition $q_0\stackrel{0}{\to }{q}_1$, followed by $q_1\stackrel{1}{\to }{q}_2$. Only $q_2$ is accepting, and all unlisted automaton transitions are absent. Staying at $q_0$ skips an arbitrary beginning; leaving it guesses that the current zero starts the final two symbols.

The word $01$ accepts along $q_0\to q_1\to q_2$. The word $1101$ accepts along $q_0\to q_0\to q_0\to q_1\to q_2$. The word $010$ rejects: a path reaching $q_2$ after $01$ cannot consume the remaining zero, while the other paths end outside $q_2$. Thus finding $01$ somewhere is insufficient; it must occur at the end.

To simulate the NFA deterministically, retain the set $S$ of all currently possible automaton states. The powerset construction updates $S$ by taking the union of the destinations of its members. Here only $\{q_0\}$, $\{q_0,q_1\}$, and $\{q_0,q_2\}$ are reachable, although the full power set has eight members. Reading $010$ gives $\{q_0\}\to \{q_0,q_1\}\to \{q_0,q_2\}\to \{q_0,q_1\}$, which rejects. In general, an $N$-state NFA yields a DFA with at most $2^N$ automaton states. Nondeterminism can simplify a description, while the powerset construction keeps the memory finite.

The second generator checks all 511 words of up to eight binary digits against the direct test of whether their final two symbols are $01$. Exactly 127 accept, and only the three listed sets of automaton states occur. In particular, the empty word rejects for this NFA.

Michael O. Rabin and Dana Scott's 1959 paper studied finite-state machines as recognizers with finite internal memory. Its section 5 defines NFAs through successful paths, and theorem 11 proves their equivalence to DFAs by the powerset construction. This gives a historical source for the distinction between many possible paths and greater recognition power: ^[ref].

A nondeterministic finite automaton, allowing the epsilon transitions used in this paper, is a tupleHere $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 $\epsilon \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=\epsilon$.

The recognized formal language isThe label of a graph path is the concatenation of its labels with all occurrences of $\epsilon$ 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.

Let $A=(Q,\{0,1\},\delta ,q_0,F)$ be a deterministic finite automaton recognizing $L$. Construct a nondeterministic finite automaton $B$ with automaton state set $Q\times \{0,1\}$. Its second coordinate records whether the extra zero has already been consumed. Start at $(q_0,0)$ and make exactly the automaton states in $F\times \{1\}$ accepting.

For each $q\in Q$, $i\in \{0,1\}$, and $a\in \{0,1\}$, include the ordinary automaton transitionAlso include the extra automaton transitionThis consumes the inserted zero without changing the simulated automaton state of $A$. At a zero in layer zero, both the ordinary and extra choices are available. There are no automaton transitions from layer one back to layer zero.

If $xy\in L$, run $A$ on $x$ in layer zero, consume the extra zero by the displayed automaton transition, and run $A$ on $y$ in layer one. The resulting run accepts $x0y$ in $B$.

Conversely, every accepting run of $B$ starts in layer zero and finishes in layer one, so it uses exactly one extra automaton transition. Split its input as $x0y$ at that move. Removing that consumed zero leaves precisely a run of $A$ on $xy$, ending in $F$. Hence $xy\in L$. The construction also permits an insertion at either end, including insertion into the empty word.

Therefore $L(B)=L^{\prime }$. Since $B$ has $2|Q|$ automaton states, $L^{\prime }$ is a regular language. This is a single-symbol insertion into a regular language.

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.

Yes: regular languages are closed under the shuffle of formal languages. The construction must allow letters common to both alphabets to be assigned to either input word.

Take complete deterministic finite automata ${\mathcal{A}}_i=(Q_i,{\Sigma }_i,{\delta }_i,s_i,F_i)$ recognizing $L_i$. Construct a nondeterministic finite automaton on $Q_1\times Q_2$ over $\Sigma ={\Sigma }_1\cup {\Sigma }_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ areBoth moves are allowed when $a$ belongs to both alphabets. They may coincide; that causes no difficulty.

For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two words $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in ${\mathcal{A}}_i$. Thus an accepting run expresses the input as an interleaving of a word of $L_1$ and a word of $L_2$.

Conversely, given such an interleaving, assign each input position to the word from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized formal language and the shuffle of formal languages, in both directions. No assumption of disjoint alphabets is needed. If one contributing word is the empty word, no move need update that coordinate; the initial pair is accepting exactly when both empty words are accepted.

Apply the powerset construction to this nondeterministic finite automaton to obtain a deterministic finite automaton. In particular,

For a deterministic finite automaton the extended transition function of a deterministic finite automaton is recursivelyThe accepted language isFor a nondeterministic finite automaton, $\hat{\delta }(q,w)$ is the set of all states reachable from $q$ while reading $w$; recursively,Thus

The powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transitionand accepting states $\{S\subseteq Q:S\cap F\ne \varnothing \}$. Induction on $|w|$ givesso the two automata accept exactly the same language. If $|Q|=m$ and $F$ has one state, exactly $2^{m-1}$ of the $2^m$ subset states contain it and are accepting, including states that may be unreachable.

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 shuffle of two formal languages consists of words whose positions can be partitioned into two subsequences, each preserving its order, with the two resulting words belonging to the respective languages. For regular languages, a product-state nondeterministic finite automaton advances exactly one coordinate for each letter. Common letters allow either choice; the powerset construction proves closure.

For a deterministic finite automaton with automaton state set $Q$ and input alphabet $\Sigma$, the function $\delta :Q\times \Sigma \to Q$ specifies the next automaton state after reading one input symbol. A nondeterministic finite automaton instead allows a set of possible next automaton states.