Finite-state machine

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 pulse sequencer can separate event capture from output timing. A short interrupt handler acknowledges the event latch and increments a pending count. An independent finite-state machine consumes one count on entering ON, changes to GAP after the pulse width, and enters IDLE only after the mandatory off interval. Even an empty queue must not bypass GAP: an arrival immediately after light-off would otherwise start too soon.

The pending count equals recorded events minus started pulses. A critical section protects its read-modify-write operations; declaring shared state as in volatile-qualified objects in C does not alone make each update an atomic operation. Separate sequencers for different channels allow simultaneous pulses while one hardware timer schedules their earliest deadline. Finite queue capacity, detector rearming and dispatch resolution remain explicit assumptions.

A Moore machine is a finite-state machine whose output depends only on the current state. In a clocked implementation, a state entered at a clock edge determines the following period's output. Specifying an initial state is necessary to define startup behavior.

A sampled toggle controller can reject short disturbances by requiring three consecutive high samples to toggle, and then three consecutive low samples before another high run is allowed to toggle. One four-bit synchronous sequential circuit stores output $z$, an armed bit $e$, and input history $p,q$. Initially $(p,q,e,z)=(0,0,1,0)$. SetThe two three-sample run detectors cannot assert simultaneously. A high run toggles once and clears $e$; only a complete low run rearms it. All right-hand sides use the old state, so the toggling event occurs at the third qualifying clock edge.

The controller has twelve distinguishable behaviours: for each $z$, three armed states count trailing highs of lengths $0,1,2$, and three disarmed states count trailing lows of lengths $0,1,2$. The run lengths are distinguished by the number of further matching samples needed before a toggle or rearm. Armed and disarmed states are distinguished by an all-high continuation. Thus at least $\lceil {\log }_{2}12\rceil =4$ state bits are required, and the displayed design attains that bound.

Store the two previous input bits in $p,q$. At the next clock edge, use $w=a\wedge p\wedge q$ and update $(p,q{)}^{\prime }=(a,p)$. The output is high exactly when the present input and previous two samples are all high. Replacing each input by its negation detects a three-sample low run. Both detectors can share the same two history bits, using $a\wedge p\wedge q$ and $\neg a\wedge \neg p\wedge \neg q$. With initial history zero, the high detector cannot trigger before three actual high samples have occurred.

A synchronous sequential circuit stores a finite collection of bits $s$, reads inputs $a$, and updates all stored bits at each clock edge according to a specified next-state function $F$. A combinational output is $G(s,a)$; an output that is itself stored is included among the state bits. An initial state is part of a complete design. These equations provide a precise implementation-level description of a finite-state machine without requiring a particular gate drawing.

A synchronous sequential circuit emitting a one-cycle pulse at the first low sample after at least two consecutive high samples. Three D flip-flops can implement $q_1^{+}=a$, $q_2^{+}=q_1\wedge a$, and $z^{+}=q_2\wedge \neg a$, with all updates using the old state. Initializing all state bits to zero excludes a false startup history. The stored output changes only at clock edges. After a detecting low sample, $q_2$ becomes zero, so the next output is zero regardless of the next input. A longer high run still ends with the same three-sample pattern.

A digital counter is a finite-state circuit that increments its stored value on each qualifying clock or event. A binary $w$-bit implementation naturally has modulus $2^w$. Dividing counted ticks by a known clock frequency gives a time interval, subject to wrap ambiguity and sampling accuracy.

A hardware timer uses a clock signal to measure intervals, commonly by a digital counter with capture or comparison facilities. A comparison event can request an interrupt or change an output directly. Counter resolution, wraparound, interrupt latency and the hardware's comparison semantics determine the timing guarantees available to software.

The displayed two-register Moore machine, initialized to $q_1{q}_0=00$, generates a one-clock pulse on a sampled high when ready, then waits for two consecutive sampled zeros before it can generate another. The codes $00,10,11,01$ represent ready, pulse, disabled and one-zero-seen respectively. From ready a high enters pulse; from pulse the next edge leaves for disabled on a high or one-zero-seen on a low. Disabled enters one-zero-seen on a low. A second consecutive low returns to ready, whereas a high returns to disabled. This transition analysis proves the output rule, the one-period duration and the immediate first-edge response after reset. It assumes a synchronous input meeting setup and hold requirements.

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 dead state of a finite automaton has no path to an accepting state. In a complete deterministic finite automaton, all dead states may be merged into one rejecting sink without changing the accepted formal language.

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.

For numbered states of a finite-state automaton, $R_{ij}^{(k)}$ is a regular expression describing paths from $i$ to $j$ whose internal states have numbers at most $k$. Splitting a path at its visits to state $k$ gives $R_{ij}^{(k)}=R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)}{)}^{\ast }{R}_{kj}^{(k-1)}$. At stage zero use individual edge labels and an empty-word option when the endpoints coincide. This proves the automaton-to-expression direction of Kleene theorem.

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$.

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.

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.

DFA minimization merges states with identical acceptance behavior for every suffix and removes unreachable states. It produces a minimal deterministic finite automaton, unique up to renaming states.

A minimal deterministic finite automaton is the result of DFA minimization. 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.

The canonical residual automaton of a regular language has its distinct left quotients of a formal language as states, initial state $L$, accepting states those containing the empty word, and letter transition $R\mapsto a^{-1}R$. It is a complete minimal deterministic finite automaton; every other complete minimal deterministic finite automaton for that language is isomorphic to it.

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.

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].

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.