12.1 Finite-State Machines

Section 2.4 showed that a combinational circuit produces its output from its current inputs only. If two identical input vectors arrive, the circuit must produce the same output both times. Many systems, however, must remember what happened earlier. A turnstile behaves differently when it is locked than when it is already unlocked. A traffic signal must know which phase it is currently displaying. This section adds exactly that missing ingredient: a small, precisely defined memory called a state.

1. From a Circuit Snapshot to a System over Time

A state is a compact description of the past information that a system still needs in order to decide what happens next. We do not record every detail of history. We record only the distinctions that can affect future behavior.

Consider a subway turnstile:

• If it is Locked, inserting a coin should unlock it.
• If it is Unlocked, pushing the arm should let one person pass and lock it again.
• Pushing a locked turnstile changes nothing.
• Inserting another coin into an unlocked turnstile also changes nothing.

The two possible states form the set

The possible inputs form an input alphabet, denoted by the Greek letter capital sigma:

Here, “alphabet” simply means a finite set of input symbols. A finite sequence of symbols from $\Sigma$ is an input string. For example,

is a string of length $3$. The empty string, containing no symbols, is written $\varepsilon$.

2. The Transition Function

A transition is one step from a current state to a next state after one input arrives. The transition function is

The symbol $\delta$, pronounced “delta,” names the function. The Cartesian product $Q\times\Sigma$ contains every pair $(q,a)$, where $q$ is a current state and $a$ is an input. Thus $\delta(q,a)$ means “the next state when input $a$ arrives in state $q$.”

For the turnstile:

The complete function can be written as a transition table:

Read one cell at a time. The row chooses the current state; the column chooses the input; the cell gives the next state. Because every row-column pair has one answer, the rule is both deterministic and complete:

• deterministic means each state-input pair has exactly one next state;
• complete means every possible state-input pair has a defined next state.

The same information can be drawn as a directed state graph. Each state is a vertex. Each transition is a directed edge labeled by its input:

(start) ──► [Locked]

[Locked]   ──coin──► [Unlocked]
[Locked]   ──push──► [Locked]       (self-loop)
[Unlocked] ──coin──► [Unlocked]     (self-loop)
[Unlocked] ──push──► [Locked]

An edge from a state back to itself is a self-loop. The arrow from the black starting marker identifies the start state, written $q_0$. Here,

This graph is not new graph theory. It reuses Chapter 11: states are vertices, inputs label directed edges, and processing an input string traces a walk.

3. Trace an Input String

To trace a machine, start at $q_0$ and process the input symbols from left to right. For

the trace is:

Therefore the final state is Unlocked. Notice the key idea: the same input, push, can lead to different next states because the current state contains memory.

A common tracing error is to jump back to the start state before every input. The start state is used only once, before the first symbol. After that, each next state becomes the current state for the following step.

Operate a physical turnstile while its state cards and trace ledger update together. Then activate maintenance mode, replay the same input string, and locate the first transition whose behavior changes.

4. Accepting Strings: Deterministic Finite Automata

Sometimes the machine must answer a yes-or-no question about an entire input string. A deterministic finite automaton, abbreviated DFA, adds a set of accepting states to the state machine:

Each part has already appeared except $F$:

• $Q$: finite set of states;
• $\Sigma$: finite input alphabet;
• $\delta$: transition function;
• $q_0\in Q$: start state;
• $F\subseteq Q$: set of accepting states.

After the whole string has been read, the DFA accepts the string if its final state belongs to $F$. Otherwise it rejects the string. Acceptance is checked only after every input symbol has been processed.

Example: binary strings ending in 01

Let $\Sigma=\{0,1\}$. We want to accept exactly the strings whose final two symbols are $01$. The machine needs only enough memory to distinguish three situations:

• $q_0$: the processed prefix does not currently end in $0$ or $01$;
• $q_1$: the processed prefix ends in $0$;
• $q_2$: the processed prefix ends in $01$.

The transition table is:

The start state is $q_0$, and the accepting set is $F=\{q_2\}$. Trace $1101$:

The final state $q_2$ is accepting, so $1101$ is accepted.

5. Extending Delta from One Symbol to a String

The original function $\delta$ consumes one input symbol. We define an extended transition function $\delta^*$ that consumes an entire string:

Here $\Sigma^*$ means the set of all finite strings over $\Sigma$, including $\varepsilon$. The definition is recursive:

where $x$ is a string already processed and $a$ is its final symbol. The first rule says that reading nothing changes no state. The second says: process the earlier part $x$, then process the last symbol $a$.

The DFA accepts $w$ exactly when

6. State Meaning as an Invariant

How do we know that the three-state machine truly recognizes strings ending in $01$? Give every state a precise state invariant—a statement that should be true after every processed prefix:

We verify the invariant in the same pattern used for loop invariants in Chapter 5:

1. Initialization: before reading input, the prefix is $\varepsilon$, so $q_0$ is correct. 2. Maintenance: for each state and each possible next symbol, the transition table moves to the state whose description matches the new suffix. 3. Conclusion: after the full string, being in $q_2$ is equivalent to ending in $01$.

This is a proof, not merely a collection of successful examples.

7. Reachability, Dead States, and Missing Behavior

A state is reachable if some input string leads from $q_0$ to that state. Graphically, ignore edge labels and run BFS or DFS from $q_0$. Any unvisited state is unreachable and can never affect the machine’s behavior from its start state.

A dead state is a nonaccepting state from which no accepting state can ever be reached. Once a DFA enters it, the current string and every possible continuation will be rejected. A dead state may have self-loops on every input, but the definition is about inability to reach acceptance, not about its drawing.

These graph checks reveal design problems:

• an unreachable state may be unnecessary;
• a missing transition makes the machine incomplete;
• two transitions with the same state and input make it nondeterministic;
• a reachable dead state may represent a permanent error condition—or an accidental trap.

8. Machines That Produce Outputs

An automaton classifies a whole string, but a controller often produces an output during operation.

In a Moore machine, output depends only on the current state. Its output function is

where $O$ is the output alphabet. A traffic-light state named NorthGreen can output “north green, east red.”

In a Mealy machine, output depends on both the current state and the current input:

The output may therefore react immediately to an input without waiting for a state change. Moore outputs are commonly written inside state nodes; Mealy outputs are commonly written on edges as input/output.

Neither model is automatically better. The choice depends on what information the output should use.

9. From a State Machine to a Sequential Circuit

A sequential circuit combines three ingredients:

1. memory bits that encode the current state; 2. a combinational next-state circuit that computes $\delta(q,a)$; 3. optionally, a combinational output circuit that computes $\lambda$.

If a machine has $|Q|$ states, then $k$ memory bits can encode at most $2^k$ states. Therefore the smallest possible number of state bits is

The ceiling $\lceil x\rceil$ means the smallest integer at least $x$. A machine with $5$ states needs

bits, because $2^2=4<5\le 8=2^3$.

The full pipeline is

This extends the Boolean circuits from Section 2.4 into machines over time: Boolean gates compute each step, while stored state carries the necessary past into the next step.

Rewrite entries in a DFA transition table, trace an input tape one symbol at a time, and launch an adversarial search that returns the shortest string exposing a disagreement with the “ends in $01$” specification.

10. What You Can Now Model

You can now translate between a transition table, a directed state graph, and a step-by-step trace; define a DFA formally; justify state meanings with invariants; identify unreachable and dead states; distinguish Moore and Mealy outputs; and connect a finite-state controller to Boolean circuitry.

The final section combines these ideas with earlier counting, probability, algorithms, trees, and graphs. Instead of studying one structure in isolation, you will design and defend an entire smart-city network whose routes, decisions, and controller states work together.