A finite state machine (FSM) is a model of a sequential system with a finite number of discrete states. At each clock edge, the system transitions to a next state determined by the current state and the inputs (next-state logic). Outputs are produced either as a function of the current state only (Moore machine) or of both state and inputs (Mealy machine). FSMs are implemented in hardware using flip-flops to hold state and combinational logic for the transition and output functions, and they model everything from traffic lights to CPU control units.
Design FSMs for simple problems like a sequence detector or vending machine controller. Draw the state diagram, derive the state transition table, assign binary encodings, and implement with flip-flops and combinational logic. Verify with timing diagrams.
A combinational circuit computes a pure function of its current inputs — it has no memory of what happened before. This is powerful but limiting. Real-world controllers — traffic lights, elevator controllers, CPU control units — need to remember where they are in a sequence. That is exactly what a finite state machine adds: a finite set of discrete states that summarize all the history the system needs.
An FSM is defined by five elements: a set of states, an input alphabet, a transition function (current state + input → next state), an output function, and an initial state. The state diagram is the most intuitive representation: circles are states, arrows are transitions labeled with inputs (and sometimes outputs). When you design an FSM for a problem, you start with the state diagram — drawing out every situation the system needs to distinguish — before thinking about gates.
The two classic variants differ in where outputs are placed. In a Moore machine, each state has a fixed output label; the output depends only on the current state. In a Mealy machine, outputs are labels on transitions; the output depends on both the current state and the current input. Moore machines are easier to reason about and produce glitch-free outputs (since outputs only change at clock edges when state changes). Mealy machines typically require fewer states to achieve the same behavior because a single state can emit different outputs depending on the input. Both models are equally powerful — you can always convert one to the other.
Hardware implementation connects directly to your combinational circuit design knowledge. The FSM has two parts: (1) next-state logic — a combinational circuit that takes the current state bits and inputs and computes what state to move to; and (2) output logic — another combinational circuit (or a direct wiring for Moore outputs) that produces the outputs. The current state is held in a register of flip-flops, one per state bit. At every rising clock edge, the flip-flops capture the next-state logic's output and the system advances to the new state.
When implementing, you must also choose a state encoding — how to represent each state as a binary number stored in the flip-flops. Binary encoding uses the minimum number of flip-flops (⌈log₂ n⌉ for n states), while one-hot encoding uses one flip-flip per state (exactly one flip-flop is 1 at all times). Binary encoding is more compact; one-hot encoding produces simpler next-state logic because checking "are we in state X?" is just reading a single flip-flop. The choice affects the complexity of your combinational logic but not the FSM's observable behavior.