A finite state machine (FSM) has a set of states, an initial state, and labelled transitions. It moves between states based on inputs and produces outputs — this is how we specify any circuit that must remember the past.

Transitions carry guards (Boolean conditions); a transition fires only when its guard is true. Convention: if no outgoing guard is true, the machine stays put (self-loops are often left undrawn). Moore machine : output depends on the state only (output written inside the state). We mostly use Moore. Mealy machine : output depends on state and input (output written on the transition). Usually fewer states but inputs affect outputs immediately/asynchronously.

From a diagram you derive an output table and a state-transition table in abstract state names, then assign binary codes. A Mealy machine typically needs fewer states for the same behaviour but its outputs glitch with the inputs (more delicate timing); a Moore machine's outputs are clean and change only with the state. Example: 'output 1 if the last two inputs were 1' needs 3 Moore states but only 2 Mealy states.

Protocol controllers, vending machines, traffic lights, the CPU's own control unit (the 'Conductor') are all FSMs.

To turn an abstract FSM into gates you must (1) possibly merge equivalent states, (2) give each state a binary code, (3) derive next-state and output logic.

State assignment options: Binary/counting : ⌈log₂(#states)⌉ bits, fewest flip-flops. Gray code : neighbouring states differ in one bit → fewer glitches, sometimes simpler output (e.g. output = one state bit). One-hot : one flip-flop per state; more FFs but simpler, faster next-state logic. State minimisation : two states are equivalent if they have the same outputs and, for every input, transition to equivalent states. Equivalent states may be merged.

The full design flow : Understand the spec (states + guarded transitions). Minimise the automaton. Abstract spec: state diagram / transition table. Assign binary codes to states. Choose memory elements (usually clocked D-FFs) for the state register. Derive next-state & output functions with Karnaugh maps. Wire the state register to the combinational logic (feedback). (Rigorous equivalence is really bisimulation, but the simple 'same output, same successors' test is in scope.)

HDL synthesis tools do exactly this; one-hot is common on FPGAs because flip-flops are plentiful and it shortens the critical path.

Once you have next-state logic, you close the feedback loop either directly (asynchronous) or through clocked flip-flops (synchronous).

Asynchronous sequential circuit: feedback straight through gates/MUXes. Pros: very fast, compact, no clock, low power. Cons: extremely glitch-sensitive — needs very careful design, especially if several state bits change at once (hence Gray coding). Synchronous circuit: feedback passes through D flip-flops driven by a common clock. Glitches in the combinational logic settle before the next edge and are harmless, provided the clock period respects the timing bound.

Max clock frequency f max ≤ 1/T with T ≥ t pd,comb + t pd,FF + t su . Faster clock = faster response, but only up to this limit. Designs may use multiple clock phases (e.g. master-slave with two clocks) to avoid races. Almost all real systems are synchronous because correctness is far easier to guarantee; asynchronous logic is reserved for special low-power or high-speed niches.

Your CPU is synchronous (one clock tree); asynchronous design appears in ultra-low-power sensors and some interconnect.