Finite-state machine

Remarks

Example: the turnstile has $Q = \set{\text{locked}, \text{unlocked}}$, $\Sigma = \set{\text{coin}, \text{push}}$, $q_0 = \text{locked}$, $\delta(q, \text{coin}) = \text{unlocked}$ and $\delta(q, \text{push}) = \text{locked}$ for both states $q$. All four clauses hold, since $Q$ is finite and $\delta$ is defined on every pair. Non-example: a counter with states $Q = \N$ and $\delta(n, a) = n + 1$ fails clause 1, because $Q$ is infinite. Adding a set $F \subseteq Q$ of accepting states gives a deterministic finite automaton. Adding an output function gives a Mealy or a Moore machine. Some authors also call nondeterministic variants, where $\delta$ is replaced by a relation, finite-state machines.