The second click means something else

A destructive button works like this: first click displays “Click again to delete”; second click deletes; any other action cancels. Feed the machine the current event click. Should it warn or delete? The event alone cannot answer. The missing fact is whether the machine is idle or armed.

Let $S$ be a finite set of states and $I$ a finite input alphabet. A transition function

$$\delta:S\times I\to S$$

computes the next state. An output function computes what the observer sees. This is the first chapter's truth-table machine again, except the row includes the current state and one output column becomes the next state.

State is not the whole history. It is the smallest summary of history needed to make every future decision. armed forgets how long the user hovered, where the pointer came from, and every earlier canceled attempt because none can affect the machine's future contract.

Output on the edge or in the room

There are two standard placements for output.

A Mealy machine computes output from current state and current input. The edge idle --click/warn--> armed emits warn during the transition. A Moore machine attaches output to the state reached: entering armed makes the warning visible.

The choice affects timing. A Mealy output may react immediately to an input but can flicker with it. A Moore output changes only with state, often making timing easier to reason about. Neither is universally better; the interface contract decides.

Two machines become one product

Suppose the delete control also has an online/offline machine. To reason about both, pair their states:

$$S = S_{confirm}\times S_{network}.$$

This Cartesian product is Chapter 5 returning as machine composition. If the first machine has three states and the second two, the naive product has six. Some pairs may be unreachable—perhaps deleted cannot coexist with offline because deletion requires an acknowledged server transition. A reachability walk from the start removes those fictional states.

Products scale poorly: ten independent two-state features have up to $2^{10}$ combined states. That is not merely an implementation issue; it is the actual option space unless invariants rule combinations out.

Merge histories the future cannot distinguish

Two states are equivalent when every possible future input sequence produces the same observable behavior from both. If no experiment can distinguish them, keeping separate names is memory without meaning.

Partition states first by immediate output. Then repeatedly split any block whose states transition into different blocks under some input. When no split remains, each block is one state of the minimal machine. This is an equivalence relation becoming a quotient, exactly as the book's earlier chapter predicted.

Where finite state runs out

• A finite machine cannot count without bound. Matching arbitrary nesting needs a stack; comparing two arbitrary substrings may need growing memory.
• A state diagram can hide an exponential product. “Only two states per feature” is not a system-wide bound.
• Reachability and minimization depend on the chosen observables. Two internal states may merge for one API and differ for another.
• A diagram documents behavior only if unspecified transitions have an explicit meaning: reject, ignore, or error.

Lessons

• State is the smallest future-relevant summary of the past.
• A transition table is Boolean algebra whose outputs include the next state.
• Mealy outputs live on transitions; Moore outputs live on states.
• Products compose machines, reachability removes impossible pairs, and behavioral equivalence removes distinctions the future cannot see.

Practice

1. Draw a machine recognizing bit strings whose last two symbols are 01. Explain why fewer remembered situations cannot suffice.
2. Convert the two-click delete Mealy machine to a Moore machine and note any new state.
3. Form the product of parity-of-ones and “last symbol was 1.” Which state pairs are reachable?
4. One day later, complete: “State is not history; state is …”

The next question is smaller than “can programs do it?”

Finite machines decide every question expressible by their finite state: run the input and stop. General programs are more powerful, but that power removes the guarantee that every analysis itself terminates. The next chapter reaches the cliff, then asks the productive question: which restriction gives the guarantee back?

References

1. Mealy. “A Method for Synthesizing Sequential Circuits.” Bell System Technical Journal, 1955. — the primary transition-output model and synthesis method
2. Moore. “Gedanken-Experiments on Sequential Machines.” Automata Studies, 1956. — the primary state-output model
3. Hopcroft, Motwani, Ullman. “Introduction to Automata Theory, Languages, and Computation.” Pearson, 2006. — standard treatment of finite automata, products, and minimization