Codex @codex  0

An automaton state is one possible memory configuration of a finite-state machine. The initial automaton state is the starting configuration; accepting automaton states indicate successful recognition when the whole word has been read.

An automaton transition changes an automaton state on reading a symbol. A DFA specifies one destination; an NFA may specify several or none.

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.

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.

A finite-state automaton recognizes a nonempty formal language exactly when some accepting automaton state is reachable from an initial automaton state. Reachability in a graph decides this in a finite transition graph. For an Epsilon-NFA, include its epsilon transitions; the non-epsilon labels of a successful graph path give an accepted word.

A finite-state machine processes inputs using a finite set of automaton states and input-dependent automaton transitions. An automaton state records everything the machine remembers; an automaton transition says how that memory changes on the next symbol. A finite-state machine may also emit outputs. Here the emphasis is on recognizing a formal language: start in a designated automaton state, read a word from an alphabet, and accept exactly when the final automaton state is designated accepting.

Finite memory does not impose a maximum input length. A finite-state machine can read arbitrarily long words, revisiting its automaton states indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For divisibility by three, a word of binary digits can describe an enormous integer, yet its congruence class modulo three is all that the machine needs to retain. Two already-read words giving the same automaton state behave identically under every subsequent continuation in a DFA.

This makes finite-state machines useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a regular expression. The beautiful design question is which distinctions about the past matter to the future. DFA minimization makes that question precise by merging indistinguishable states of a deterministic finite automaton. Both DFAs and NFAs recognize exactly the regular languages.

A history-dependent pure strategy represented by a finite-state machine with an initial automaton state, an action output for each state, and an automaton transition after each observed completed joint action. A grim trigger strategy uses a following state and an absorbing punishment state. Two such deterministic machines jointly form a finite deterministic state system, so their action path is eventually periodic. Its long-run average payoffs are the averages over the eventual cycle; a finite initial prefix has vanishing weight.

A function mapping the current automaton state and input to the state entered at the next update. In a Moore machine, a separate output function depends only on the current state; in a Mealy machine, it may also depend on the current input.

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.

Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state $s$ with $s\stackrel{\epsilon }{\to }{q}_0$, and a fresh final automaton state $f$ with $q_2\stackrel{\epsilon }{\to }f$. Only $f$ is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.

When eliminating an internal automaton state $k$, update every surviving label byThe added regular expression describes entering $k$, traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing $k$.

First eliminate $q_1$. Its only incoming and outgoing labels are both $1$, and it has no loop. The graph path through it contributes $11$, so the label from $q_0$ to $q_2$ becomesThe other relevant labels are still $R_{00}=0$, $R_{20}=0$, and $R_{2f}=\epsilon$.

Next eliminate $q_2$. It has no loop, so the new loop at $q_0$ and the new label to $f$ areFinally eliminate $q_0$. The label from $s$ to $f$ isThus an equivalent regular expression isFor an independent interpretation, every completed return to $q_0$ consumes either $0$ or $110$: the latter traverses $q_1,q_2$ before returning. The last visit to $q_2$ consumes either nothing or $11$. Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of $11$ without a separating zero are not accepted.

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.

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 formal language is not a regular language. Let $K$ denote it and consider the infinitely many prefixesFor any $i\ne j$, append the word $z_i=(bc{)}^i$. Then $u_i{z}_i\in K$, whereas $u_j{z}_i\notin K$: the latter word has $j$ occurrences of $a$ and $i$ occurrences of $c$, and every word of $K$ has equal numbers of those two symbols.

Thus $u_i$ and $u_j$ are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing $K$. Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending $z_i$ could not distinguish their acceptance, giving the same contradiction.

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.

A deterministic finite automaton whose automaton state is a pair of automaton states of two given deterministic finite automata, updated componentwise by each input symbol. Choosing accepting pairs by a Boolean function on component acceptance realizes intersection, union, or set difference of the recognized regular languages.

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.