From the state diagram to the table and the flip-flop equations, with a sequence detector
Each arrow carries the value of input x that causes it; in Mealy, also the output it produces ("input/output"). In Moore the output is inside the state, and the double-circled states are the ones that give z = 1.
A finite state machine is a sequential circuit that is, at any moment, in one of a limited number of states. The state sums up everything that matters about the past. On each clock edge it moves to a new state that depends on the current state and the inputs. It is built from a register of flip-flops, which holds the state, and two blocks of combinational logic: one computes the next state and the other the outputs.
It is the orderly way to design any automated sequence: a traffic light, the control of an automatic door, a vending machine, the protocol of a serial port or the stages of a washing cycle. In a PLC it is programmed the same way with GRAFCET or with steps in ladder, and in a microcontroller with a switch on a state variable.
| Moore | Mealy | |
|---|---|---|
| The output depends on | The state only | The state and the inputs |
| Where the output is drawn | Inside each state | On each arrow, "input/output" |
| Number of states | Usually needs a few more | Usually needs fewer |
| Response | The output changes on the next clock edge | The output changes as soon as the input changes |
| Output | Stable for the whole cycle, no glitches | Can glitch if the input does |
Compare both types in the simulator with the same sequence: the Mealy detector gives z = 1 in the same cycle as the last bit arrives, and the Moore one a cycle later, once it has entered the final state. If the output of a Mealy machine feeds another synchronous circuit, that delay appears anyway when it is registered.
With overlapping, the last bits of a detected sequence can be the start of the next one: looking for 1011 in 1011011, it is detected twice. Without overlapping, after each detection the machine starts over and finds only one. To decide which state to return to when a bit arrives that does not fit, look for the longest part of what was received that matches the beginning of the sequence; it is the same idea used by the KMP text search algorithm.
A traffic light for cars with a pedestrian button is a Moore machine: the lights depend only on the state. A timer gives the "time elapsed" signal and the button press is latched until it is served.
| State | Car lights | Pedestrian lights | Moves on when |
|---|---|---|---|
| S0 Green | Green | Red | A pedestrian has pressed and the minimum green time has elapsed |
| S1 Amber | Amber | Red | Amber time elapsed |
| S2 Red | Red | Green | Pedestrian crossing time elapsed |
| S3 Clearance | Red | Flashing green | Clearance time elapsed; back to S0 |
Four states are encoded with two flip-flops. The outputs are functions of Q1 and Q0, for example car green = Q1'·Q0' and pedestrian red = Q1'.
Related: latches and flip-flops, Karnaugh map, logic gate simulator and ladder simulator.