Finite-state_machine - Wikiparency

# Finite-state machine ## Microsim (three.js) <div class="microsim-player">  <p class="wt-pending"><strong>Microsim staged, not yet on the CDN.</strong> <code>Finite-state_machine.html</code> is built and deploy-ready in <code>Microsims for Dissemination/</code>, but the Netlify project still serves the geometry+spintronics set only. The player is disabled until the deploy lands; the explanatory text below is unchanged.</p>   </div> *The finite-state machine is the smallest useful model of computation in the ALGORITHM hub — the abstraction realized by [[Sequential_logic]], rooted in Switching circuit theory, and beating inside every clocked Synchronous circuit and CPU control unit. Feed it a stream of inputs and watch all memory collapse to a single active state.* > A finite-state machine (FSM) is an abstract machine that is always in exactly one of a finite number of states and jumps to a new state whenever it receives an input. This microsim renders the classic turnstile: it starts **Locked**, and you drive it by pressing **Coin** and **Push** to watch the highlighted state flip between Locked and Unlocked. Because the machine remembers nothing but its current state, the same button can act differently depending on where you are — pressing Push while Unlocked locks the gate, while pressing Push when already Locked does nothing. That input-dependent behavior, built from a single bit of memory, is the whole idea. ## About this microsim The sim draws the turnstile's state diagram — two nodes, Locked and Unlocked, joined by labeled transition arrows — and highlights whichever state is active. **Coin** applies the coin input and **Push** applies the push input, so you can hand-drive any sequence and watch the highlight travel along the matching arrow; try Push, Push, Coin, Push to feel how identical clicks land differently. **Step (random)** fires one randomly chosen input, **Auto-Play** streams random inputs so the active state performs a random walk across the diagram, and **Reset** returns the machine to its Locked start. Every control is a button — there are no sliders. ## Related microsims - [[Sequential_logic]] — the circuit family whose behavior an FSM abstractly describes - Synchronous circuit — clocked hardware that stores the current state in flip-flops - Combinational logic — implements the next-state and output functions between clock edges - Switching circuit theory — the historical origin of modeling switches as states - Truth table — the tabular form the transition function generalizes - Microcode — CPU control units realized as large finite-state machines - Asynchronous circuit — related ALGORITHM microsim - Complex programmable logic device — related ALGORITHM microsim - Decidability (logic) — related ALGORITHM microsim - [[Fuzzy_control_system]] — related ALGORITHM microsim - Hardware description language — related ALGORITHM microsim - Macrocell array — related ALGORITHM microsim - Register-transfer level — related ALGORITHM microsim - Stored-program computer — related ALGORITHM microsim - Temporal logic — related ALGORITHM microsim ## Links (Wikipedia order)  `Abstract_machine` · `Abstract_state_machine` · `Addison-Wesley` · `Alternating_finite_automaton` · `Application-specific_integrated_circuit` · `Asynchronous_circuit` · `Automata-based_programming` · `Automata_theory` · `Biology` · `Boolean_algebra` · `Boolean_circuit` · `Capacitor` · `Chomsky_hierarchy` · `Christos_Papadimitriou` · `Circuit_diagram` · `Combination_lock` · `Combinational_logic` · `Communicating_finite-state_machine` · `Compiler` · `Compilers:_Principles,_Techniques,_and_Tools` · `Complex_programmable_logic_device` · `Computational_linguistics` · [[Computer_architecture]] · [[Computer_hardware]] · `Computer_memory` · [[Computer_science]] · `Context-free_grammar` · `Context-free_language` · `Context-sensitive_grammar` · `Context-sensitive_language` · [[Control_system]] · `Control_table` · [[Control_theory]] · `DEVS` · `DFA_minimization` · `David_Harel` · `Decider_(Turing_machine)` · `Decision_table` · `Derick_Wood` · `Deterministic_acyclic_finite_state_automaton` · `Deterministic_context-free_grammar` · `Deterministic_context-free_language` · `Deterministic_finite_automaton` · `Deterministic_pushdown_automaton` · `Digital_audio` · `Digital_cinematography` · `Digital_electronics` · `Digital_photography` · `Digital_radio` · `Digital_signal` · `Digital_signal_(signal_processing)` · [[Digital_signal_processing]] · `Digital_television` · `Digital_video` · `Directed_graph` · [[Electrical_engineering]] · `Electronic_circuit` · `Electronic_component` · `Electronic_literature` · `Elevator` · `Embedded_pushdown_automaton` · `Emitter-coupled_logic` · `Empty_string` · `Event-driven_finite-state_machine` · `Field-programmable_gate_array` · `Field-programmable_object_array` · [[Finite-state_machine]] · `Finite-state_transducer` · `Finite_Automata_(band)` · `Finiteness` · [[Flip-flop_(electronics)]] · `Formal_equivalence_checking` · `Formal_grammar` · `Formal_language` · `Gate_equivalent` · `Generalized_nondeterministic_finite_automaton` · `Generic_Array_Logic` · `Hardware_acceleration` · `Hardware_description_language` · `Harry_R._Lewis` · `Hidden_Markov_model` · `High-level_synthesis` · `Hybrid_integrated_circuit` · `Implication_table` · `Indexed_grammar` · `Indexed_language` · `Inductor` · `Input_(computer_science)` · `Integrated_circuit` · `Introduction_to_Automata_Theory,_Languages,_and_Computation` · `Jeffrey_Ullman` · `John_Hopcroft` · `Lexical_analysis` · `Linear_bounded_automaton` · `Linguistics` · [[Logic]] · [[Logic_gate]] · `Logic_in_computer_science` · `Logic_synthesis` · `Macrocell_array` · `Markov_chain` · `Mealy_machine` · `Memory_cell_(computing)` · `Metastability_(electronics)` · `Mixed-signal_integrated_circuit` · `Model_of_computation` · `Moore_machine` · `National_Institute_of_Standards_and_Technology` · `Nested_stack_automaton` · `Nested_word` · `Nondeterministic_finite_automaton` · `Partial_function` · `Petri_net` · `Philosophy` · `Place_and_route` · `Placement_(electronic_design_automation)` · `Powerset_construction` · `Printed_circuit_board` · `Printed_electronics` · `Processor_register` · `Programmable_Array_Logic` · `Programmable_logic_array` · `Programmable_logic_controller` · `Programmable_logic_device` · `Pushdown_automaton` · `Quantum_finite_automaton` · `Rajeev_Motwani` · `Ravi_Sethi` · `Recursive_language` · `Recursively_enumerable_language` · `Register-transfer_level` · `Regular_grammar` · `Regular_language` · `Relay` · `Resistor` · `Routing_(electronic_design_automation)` · `Runt_pulse` · `SCXML` · `Semiautomaton` · `Semigroup_action` · `Semiring` · [[Sequential_logic]] · `Shortest_path_problem` · [[Software_engineering]] · `Specification_and_Description_Language` · `Star-free_language` · `State-transition_table` · `State_(computer_science)` · `State_diagram` · `State_encoding_for_low_power` · `State_machine_(disambiguation)` · `State_pattern` · `String_(computer_science)` · `Switching_circuit_theory` · `Synchronizing_word` · `Synchronous_circuit` · `Telephony` · `Tensor_Processing_Unit` · `Theoretical_computer_science` · `Theory_of_computation` · `Thread_automaton` · `Three-dimensional_integrated_circuit` · `Token_coin` · `Traffic_light` · `Transaction-level_modeling` · `Transformation_semigroup` · [[Transistor]] · `Transistor–transistor_logic` · `Transition_system` · `Tree-adjoining_grammar` · `Tree_automaton` · `Tree_stack_automaton` · `Truth_table` · `Tuple` · `Turing_machine` · `Turnstile` · `UML_state_machine` · `Unified_Modeling_Language` · `Unrestricted_grammar` · `Vending_machine` · `Video_game_programming` · `Virtual_finite-state_machine` ## Overview A finite-state machine is a foundational and widely used model of computation. It grew out of 1940s–1950s work by Warren McCulloch and Walter Pitts on nerve nets and by George Mealy (1955) and Edward Moore (1956) on sequential machines. In the theory of computation FSMs sit at the bottom of the Chomsky hierarchy: deterministic and nondeterministic finite automata recognize exactly the regular languages, the automaton side of Kleene's theorem. Having no unbounded memory, they are strictly weaker than pushdown automata and Turing machines and cannot match arbitrarily nested brackets. That same simplicity makes them ubiquitous — vending machines, traffic lights, network protocols, lexical analyzers, and the control units inside a CPU are all FSMs. ## How it works Formally, a deterministic finite acceptor is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$: a finite state set $Q$, an input alphabet $\Sigma$, a transition function $\delta: Q \times \Sigma \to Q$, a start state $q_0$, and accepting states $F \subseteq Q$. Machines that also emit symbols are transducers — a **Moore** machine's output depends only on the state ($\lambda: Q \to \Delta$), a **Mealy** machine's on state and input ($\lambda: Q \times \Sigma \to \Delta$). This turnstile uses $Q=\{\text{Locked},\text{Unlocked}\}$, $\Sigma=\{\text{coin},\text{push}\}$, and $q_0=\text{Locked}$, with: | Current state | Input | Next state | |---|---|---| | Locked | coin | Unlocked | | Locked | push | Locked | | Unlocked | coin | Unlocked | | Unlocked | push | Locked | Treating each press as one symbol, the machine consumes an input string of length $n$ in $O(n)$ time while storing only $\lceil\log_2|Q|\rceil = 1$ bit. Determinism means $\delta$ returns exactly one next state per pair; a nondeterministic version can always be made deterministic by the subset construction, at a worst case of $2^{|Q|}$ states. ## Controls -> what each maps to | Control | Maps to | Range / values | Meaning | |---|---|---|---| | Coin | Input symbol *coin* | single press | Applies $\delta(q,\text{coin})$; unlocks a Locked gate, no-op when Unlocked | | Push | Input symbol *push* | single press | Applies $\delta(q,\text{push})$; locks an Unlocked gate, no-op when Locked | | Step (random) | One random input | single press | Draws coin or push at random and applies one transition | | Auto-Play | Continuous random input stream | on / off toggle | Repeatedly steps, driving a random walk over the state graph | | Reset | Return to $q_0$ | single press | Restores the initial Locked state | ## Learning objective After playing, a learner can predict the next state of a deterministic FSM from its current state and the next input, and explain why one input yields different results in different states. ## Limits and connections The sim is a two-state Moore machine whose output is just the current lock state, so it cannot illustrate nondeterminism, state minimization, or large output alphabets, and real controllers may have thousands of states. Yet the same formalism scales straight to hardware, where the next-state logic is combinational and the current state lives in clocked flip-flops — the bridge from this diagram to a real Synchronous circuit. ## Poster & source <div class="microsim-fallback">  <p><em>Live microsim · <a href="https://wikitube-3d-microsims.netlify.app/Finite-state_machine.html">open full</a> · source: Microsims for Dissemination/ALGORITHM_microsims/Finite-state_machine.html</em></p> </div>  *Built to the [[WT!Three_js_Microsim_Master_Class|three.js Master Class]].*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Finite-state_machine) : [Wikitube](https://en.wikitube.io/wiki/Finite-state_machine) ## Previous hub tags Tree parents: [[Dynamical_system]] · [[Feedback]]. Legacy hubs: `ALGORITHM`. --- *Sources: 1 legacy note. Minted wave 1, 2026-07-30 (v1.6 order).*