Finite-state automaton

A finite-state automaton recognizes a formal language by updating one of finitely many states as it reads each input symbol.

A finite directed automaton whose edge labels are regular expressions rather than individual letters. A path accepts concatenations of words in its successive labels, with choices over all accepting paths combined by union.

To remove an internal state $k$, replace each surviving label by $R_{ij}\cup R_{ik}(R_{kk}{)}^{\ast }{R}_{kj}$. The added term accounts for entering $k$, traversing its loop any number of times, and leaving it. Fresh initial and final states allow all old states to be eliminated, producing a regular expression for the same language.

A deterministic finite automaton has finitely many states and one transition for each state-symbol pair.

For a transition function $\delta :Q\times \Sigma \to Q$, defineThe accepted language is $\{w:\hat{\delta }(q_0,w)\in F\}$.

A state is accessible when some input word takes the initial state to it. Removing inaccessible states preserves the accepted language.

Two states are indistinguishable when every continuation is accepted from both or rejected from both. Distinguishable states admit at least one suffix with different acceptance outcomes.

Indistinguishability is a right-invariant equivalence relation. The quotient has states $[q]$, transition $[q]\mapsto [\delta (q,a)]$, initial state $[q_0]$, and accepting classes represented by accepting states. It accepts the original language and has no two distinct indistinguishable states.

A deterministic automaton is irreducible when every state is accessible and every pair of distinct states is distinguishable.

An irreducible deterministic automaton has the fewest states among deterministic automata for its language and is unique up to isomorphism. Its states are the Myhill--Nerode classes.

In a minimal deterministic finite automaton accepting a finite language, any state lying on a nonempty directed cycle is the unique rejecting sink state. It cannot reach an accept state, since traversing the cycle arbitrarily many times would produce infinitely many accepted words. Every state reachable from it also rejects every continuation, so minimality forces all such states to be the same state.

For a positive integer $m$, binary strings can be tested for divisibility by $m$ with residue states $0,\dots ,m-1$ and transitionThe initial and accepting residue is zero. For $m=7$, all seven states are reachable and pairwise distinguishable, so this automaton is minimal.

An accessible automaton over one letter consists of a directed tail entering one directed cycle. Its minimal quotient is obtained by merging positions having the same future binary acceptance sequence.

To recognize prescribed parities of several symbol counts, use one state for each tuple of parities. Reading a tracked symbol toggles its coordinate and leaves all other coordinates unchanged. For two tracked symbols this gives four states indexed by ${\mathbb{Z}}_2^2$.

To recognize words having at most $m$ consecutive copies of a symbol, use states $0,1,\dots ,m$ recording the current run length and one rejecting sink. Another symbol resets the run length to zero, while the $(m+1)$st consecutive copy enters the sink.

A nondeterministic finite automaton assigns a set of possible successor states to each state-symbol pair and accepts when at least one run ends in a final state.

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

The epsilon closure of a state set $S$ consists of every state reachable from $S$ using zero or more epsilon transitions.

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.

Without epsilon transitions, defineA word is accepted when the set reached from the initial state meets the final set.

For $w=a_0\cdots a_{n-1}$, a witnessing sequence from $p_0$ to $p_n$ satisfies $p_{i+1}\in \Delta (p_i,a_i)$. Induction on word length shows that $q^{\prime }\in \hat{\Delta }(q,w)$ exactly when such a sequence runs from $q$ to $q^{\prime }$.

The powerset construction turns an NFA with state set $Q$ into a DFA with state set $\mathcal{P}(Q)$, transitionand accepting subsets that meet the NFA final set.

In the convention used here, a Brzozowski NFA has one final state, every state can reach it, and each word labels a path to it from exactly one starting state.

For distinct accessible subset states, choose a state in their symmetric difference. A word taking it to the unique final state accepts from one subset; uniqueness of the starting state prevents acceptance from the other. Thus the accessible part of the subset automaton is irreducible.