Setup. Figure 9.43 is an 8-row primitive flow table for an asynchronous Moore-like FSM. Inputs $w_2 w_1$, rows $A$–$H$, output $z$ varies per row. The dramatic claim: this 8-row table reduces all the way down to just 2 states via partitioning + merger, but the result is a Mealy FSM (some output depends on input not just state).

Stage 1 — Partitioning. Group by output and refine by next-state successors:

So the partitioning step proves $A \equiv F$ and $B \equiv E$. Replace $F$ with $A$ and $E$ with $B$ → 6-row table (Figure 9.44 in the textbook):

Stage 2 — Merger diagram. Build a graph where each row is a vertex and each compatible pair (no conflicting next-state entries; Mealy-output compatibility) is an edge. From Figure 9.45:

• $A$, $B$, $C$ form a clique → can all merge into a single new state (call it $A$)
• $D$, $G$, $H$ form a clique → merge into a single new state (call it $D$)

Two cliques cover all 6 vertices → 2 states total.

Why this can collapse to 2 states even though outputs differ: the merge $\{D, G, H\}$ contains states with $z=1$ ($D, H$) and one with $z=0$ ($G$). That's fine in a Mealy FSM — the output is then a function of the merged state plus current input ($z$ depends on which "sub-row" you're acting like for that input). Within the merged row, each input column inherits the output from whichever original row stable-stated there. The stable-state outputs survive; the unstable-transition outputs become Mealy outputs.

Resulting 2-state Mealy table (Figure 9.46):

The lesson: primitive flow tables look intimidatingly large, but the underlying state-transition graph is often almost trivial. Two-step reduction (partition + merger) extracts the minimum-state realization. Switching from Moore to Mealy framing during merger is a common trick — it relaxes the output-equality constraint and unlocks merges that would otherwise be blocked.

Figure 9.55a — original 4-state Moore flow table:

The trouble: labeling the 8 stable cells 1–8 and tracing transitions reveals every pair of states has a direct transition — A↔B, A↔C, A↔D, B↔C, B↔D, C↔D. A 2-cube has only 4 vertices and 4 edges, so no 2-bit assignment can give all 6 pairs Hamming distance 1. 2-cube embedding is impossible.

The fix: move to a 3-cube. Three state bits give 8 vertices; we use 4 for the original states and 3 for new unstable intermediate vertices that break the impossible direct paths.

Step 1 — pick a base assignment: $A=000$, $B=001$, $C=100$, $D=010$. Direct cube-edge pairs (Hamming-1):

• A↔B (000↔001) ✓ ; A↔C (000↔100) ✓ ; A↔D (000↔010) ✓
• B↔D (001↔010) ✗ — distance 2; need intermediate
• B↔C (001↔100) ✗ — distance 2; need intermediate
• C↔D (100↔010) ✗ — distance 2; need intermediate

Step 2 — insert unstable vertices on each long path:

The 8th vertex 111 stays unused.

Step 3 — modify the flow table. Whenever a transition would have crossed a long path, redirect it through the matching intermediate. For example, B→D on input $w_2w_1=10$ now becomes B→E (next-state E in row B); E is set up so that with input still 10, E→D (next-state D in row E). The table grows to 7 rows but the new entries are all "transit cells" that aren't stable for any input.

Step 4 — derive the excitation table. With 3 state variables $y_3 y_2 y_1$, write the next-state codes $Y_3 Y_2 Y_1$ for every (state, input) cell using the assignment above. The excitation entries can then be K-mapped to obtain the next-state logic, which drives the three feedback loops back to the state-bit latches/flip-flops.

What problem 9.26 asks specifically:

1. Identify which of the 6 state-pairs need intermediates (the 3 long paths).
2. Choose a 3-cube assignment that puts each state on a distinct vertex and provides single-bit-change paths between all required pairs (the assignment above is one valid solution).
3. Insert E, F, G as unstable transit rows in the flow table.
4. Build the excitation table (next-state binary codes) for the 7-row modified flow table.

Why this matters: race-free state assignments are mandatory in asynchronous design — if two state bits change simultaneously, the FSM may briefly visit an unintended cube vertex, which is itself a stable state in the wrong row, and the circuit can deadlock. By breaking every multi-bit transition into single-bit hops through transit states, only one bit ever changes at a time and races become impossible.

The circuit (Figure 9.76) realizes an asynchronous FSM with state variables $y_1, y_2$, inputs $w_1, w_2$, output $z$. Logic:  $Y_1 = w_1\overline{w_2} + \overline{w_2}\,y_1 + w_1 y_1 \overline{y_2}$,  $Y_2 = w_2 + w_1 y_1 + w_1 y_2$,  $z = y_2$.

Step 1 — build the excitation table. For each combination of $(y_2 y_1, w_2 w_1)$, evaluate the next-state codes $(Y_2 Y_1)$ and the output $z$:

Step 2 — identify stable states. A cell is stable iff $(Y_2 Y_1) = (y_2 y_1)$ for that input. Mark them (bold below in Figure 9.77's flow-table form). Each row corresponds to a present-state code.

Step 3 — name the states. Replace each binary code with a letter: $A = 00$, $B = 01$, $C = 10$, $D = 11$. Then:

Step 4 — check for safe-race transitions. A "race" occurs when both state variables change simultaneously in response to one input change. From the excitation table, identify cells where both $Y_2$ and $Y_1$ differ from the present $y_2$ and $y_1$. Examples:

• $y_2 y_1 = 01, w_2 w_1 = 11$: next is $11$ — both bits change ($y_2: 0\to 1$, $y_1: 1\to 1$? actually only $y_2$ changes here, so single-bit). Inspect each entry carefully.
• $y_2 y_1 = 11, w_2 w_1 = 10$: next is $10$ — only $y_1$ changes, single-bit. Safe.

Definition: safe race. A race is "safe" (non-critical) if the FSM eventually settles in the correct stable state regardless of which state variable changes first. A race is critical (unsafe) if intermediate states are stable for the same input — the circuit may get stuck. The textbook usually solves the analysis problem by tabulating each multi-bit transition and verifying that all single-bit-change paths converge to the same destination.

What problem 9.31 asks:

1. Plug $w$ and $y$ values into $Y_1$ and $Y_2$ to fill the excitation table.
2. Convert to a labeled flow table; identify stable cells.
3. Check every multi-bit-change cell for race safety.
4. Confirm output $z = y_2$ matches expected behavior in each row.

Spec. Asynchronous FSM with two inputs $D$ (dime sensed) and $N$ (nickel sensed). Output $z=1$ when at least 10 ¢ has been collected (dispense). 15 ¢ overpay gives no change. Asynchronous-design rule: only one input variable may change at a time, so $DN=11$ is unreachable.

Six-state initial state diagram (Moore-type, Figure 9.26a):

• A ($z=0$) — reset, 0 ¢. $N=1$→B; $D=1$→C
• B ($z=0$) — 5 ¢, sensor still showing nickel. When $N$ clears → D
• C ($z=1$) — 10 ¢ via dime, sensor still showing dime. When $D$ clears → A
• D ($z=0$) — 5 ¢, sensor idle. $N=1$→E; $D=1$→F
• E ($z=1$) — 10 ¢ via 5+5. When sensor clears → A
• F ($z=1$) — 15 ¢ via 5+10. When sensor clears → A

Primitive flow table (Figure 9.26b) — one stable state per row (bold = stable); dashes are don't-cares (forbidden $DN=11$ and impossible-transition entries):

What the problem asks (two-step reduction):

1. Partitioning: group by output and refine. The output partition is $\{A, B, D\}$ ($z=0$) and $\{C, E, F\}$ ($z=1$). Refining by next-state behavior across columns produces the equivalence pair $E \equiv C$ (both stable on $DN=01$/$10$ respectively but with the same "go to A on 00" pattern) and other compatible-state findings.
2. Row merging: combine rows whose specified next-state entries don't conflict (don't-cares can be filled either way). After merging, the table collapses from 6 rows to 4.

Result (Figure 9.27 in the textbook). The 4 surviving states correspond to {idle, 5 ¢ collected with sensor cleared, 5 ¢ with sensor active, ≥10 ¢ collected}. Stable-state pairs that originally distinguished "10 ¢ via single dime" vs "10 ¢ via 5+5" merge because the asynchronous output and stable-state behavior are identical from that point on.

Why primitive tables are reducible: the one-stable-per-row format is verbose by construction. Many of those rows turn out to be doing the same thing once you allow don't-cares to be filled in. The two-step partition-then-merge procedure is the canonical asynchronous-FSM reduction algorithm.

Figure 9.52a — original 4-state Moore flow table (bold = stable, "—" = unspecified):

Counting stable-state cells: A×2, B×2, C×2, D×1 → 7 stable instances.

Figure 9.52b — relabeled with stable-instance numbers 1–7 (each stable cell gets a unique label so we can name transitions by their destination):

Why the relabeling helps: a transition like "C → A" in column 00 ends at the stable cell labeled 1 — so we annotate that arrow with "1". Multiple transitions ending at the same stable instance can share a label.

Step 1 — first transition diagram (assignment A=00, B=01, C=11, D=10). Connect every pair of states that exchange transitions; the offending arrows are diagonals on the 2-cube (Hamming distance 2):

• A↔C diagonal carries labels 1 (C→A) and 7 (A→C)
• B↔D diagonal carries labels 3 (D→B) and 7 (B→D)

Label-7 paths (transitions to stable D) have alternative routes via other states — they can be re-routed off the diagonal. But labels 1 and 3 are stuck on diagonals — no alternate path. So this assignment fails.

Step 2 — try swapping B and C codes (A=00, B=11, C=01, D=10). Now A↔B is the diagonal and B↔D becomes adjacent. Recheck:

• C→A: 01 → 00, Hamming-1 ✓
• D→B: 10 → 11, Hamming-1 ✓
• A→B (label 4): 00 → 11, Hamming-2 ✗ — still diagonal

Step 3 — exploit the unspecified entry. Row D, column 01 is "—". Fill it with $B$ (so D becomes a "pass-through" for the 01-input). Now the transition $A \to B$ on input 01 can be re-routed as $A \to D \to B$ (two single-bit hops: 00→10→11). The diagonal A↔B disappears from the transition graph because nobody needs it any more.

Augmented transition diagram (Figure 9.53c):

All edges are single-bit changes. The 2-cube embedding works → state assignment A=00, B=11, C=01, D=10 is race-free.

Why a Mealy model is needed afterward. Several transitions now route through unstable intermediate states (e.g., A→D→B). If the output were strictly $f(\text{state})$ (Moore), the FSM would briefly show D's output (11) while passing through it on the way to B (whose output is 01). That's an output glitch. To suppress glitches, the modified flow table (Figure 9.54a) re-specifies the output column-by-column as a function of $(\text{state}, w)$: in unstable cells, the output is forced to match the eventual stable destination's output, not the unstable transition state's output.

The general technique:

1. Number stable instances → cleaner transition labeling.
2. Draw transition graph; identify offending diagonals.
3. Re-route diagonal transitions through alternative states whenever a label has multiple paths available.
4. Use unspecified entries to add compatible alternative paths (this is the key insight — don't-cares aren't just for next-state simplification, they create new transition paths too).
5. Switch to Mealy outputs to suppress glitches in the now-extended transition routes.

Same FSM as in problem 9.26 (Figure 9.55), where the 4-state transition diagram has all 6 state-pairs requiring transitions and can't embed on a 2-cube.

Figure 9.55a — flow table (stable states underlined; output $z_2 z_1$):

Every pair of states has at least one transition (the diagram is $K_4$), so any 2-bit assignment forces at least one Hamming-2 step — that's the diagonal edge. Adding a third state-bit gives a 3-cube with 8 vertices, and the trick is to use those extra vertices to break the diagonals into single-bit hops.

Problem 9.26 solves it by inserting 3 extra unstable states (E, F, G). This problem solves it differently: replicate each of the 4 states as an equivalent pair, giving 8 states total — exactly enough to fill the 8 vertices of a 3-cube.

The state-splitting recipe:

1. For each original state $X$, introduce a clone $X'$ with the same outputs and the same stable-cell set. Both $X$ and $X'$ are valid stable states.
2. Each transition that originally entered $X$ may instead enter $X'$, depending on which choice gives a single-bit code change.
3. Pick a 3-bit assignment for the 8 states such that every required (state, target) edge is on a cube edge (Hamming-1).

Sample assignment that works: $A=000$, $A'=001$, $B=011$, $B'=010$, $C=110$, $C'=111$, $D=101$, $D'=100$. Walk the cube vertices in Gray-code order — each consecutive pair differs by one bit, so every "long" diagonal in the original 4-state graph can be replaced by routing to the appropriate clone of the destination.

Concrete example: A→B normally requires a 2-bit jump. Instead, route A=000 → A'=001 (1-bit) → B=011 (1-bit) → B'=010 (1-bit). The transit goes through a clone (A') and lands in the right state's clone (B'). Outputs match, so the user never knows which clone they're in.

Trade-off vs. the unstable-state approach (problem 9.26):

What 9.27 specifically asks:

1. Pair each of A, B, C, D with a clone $A', B', C', D'$.
2. Assign 3-bit codes so every transition is Hamming-1.
3. Modify the flow table: replace 4 rows with 8 rows; specify which clone the transitions enter.
4. Verify the new transition diagram has no diagonal paths.

When to choose which approach: state-splitting tends to give simpler next-state logic (the symmetry helps K-map minimization), but doubles the row count and uses all cube vertices. Insertion of unstable transit states (9.26) has fewer rows but the transit cells are explicit "non-stable" places that must be carefully verified to never permanently latch.

Figure 9.65a — the POS circuit: $f = (x_1 + x_2)(\overline{x_2} + x_3)$ realized as two OR gates feeding an AND gate. Internal nodes $p = x_1 + x_2$ and $q = \overline{x_2} + x_3$.

The hazard scenario. Set $x_1 = x_3 = 0$ and toggle $x_2$ from 0 to 1. The function should stay at $f = 0$ throughout (both inputs to the AND cannot simultaneously be 1 in steady state):

The glitch. During the $x_2: 0 \to 1$ transition, $p$ rises from 0 to 1 (the OR sees $x_2$ go up) before $q$ falls from 1 to 0 (because the inverter on $\overline{x_2}$ adds an extra delay before the second OR sees the change). For a brief window $p = q = 1$, so $f = 1$. The output exhibits a $0 \to 1 \to 0$ glitch — a static-0 hazard.

Why POS circuits hazard on adjacent 0s. In a POS circuit, the AND of OR-terms produces 0 only when at least one OR-term is 0. A hazard occurs at the boundary between two K-map 0-cells where no single sum-term covers both — momentarily both terms can be 1, giving $f = 1$.

The fix. Add a redundant sum-term $(x_1 + x_3)$ that covers both adjacent 0-cells (it is 0 only when $x_1 = x_3 = 0$). With this extra term, every transition between adjacent 0s leaves at least one OR-term at 0 throughout the transition:

Cost of removing the hazard: one extra OR2 gate plus one input to the AND. The extra gate is logically redundant — it does not change the function — but it bridges the gap that allowed the glitch.

Dual rule (memorize):

• SOP circuits: hazards on transitions between adjacent 1-cells. Fix: add product term covering each pair of adjacent 1s.
• POS circuits: hazards on transitions between adjacent 0-cells. Fix: add sum term covering each pair of adjacent 0s.

Figure 9.81 — original 8-row primitive flow table (Moore-type, output $z$ depends only on state):

Stage 1 — Partitioning by output groups (refine until stable):

Equivalence found: $A \equiv G$. Merge them into a single state (call it $A$). Result: 7-row table (Figure 9.82).

Stage 2 — Merger diagram on the 7-row reduced table identifies these compatible-pair merges:

• $A$ and $E$ — same don't-care pattern, compatible next-states
• $C$ and $F$ — compatible next-states
• $D$ and $H$ — compatible next-states (both produce $z=1$, both go to $B$ on input 11)

After merging: 4-state table (Figure 9.84). Relabel for state assignment.

Stage 3 — State assignment. The relabeled 4-state transition diagram (Figure 9.86a) has one diagonal: D→A on some input, labeled "1" — Hamming-2 jump.

The fix: exploit a don't-care entry to route the diagonal D→A through state C (Hamming-1 hops): $D \to C \to A$. After this re-routing (Figure 9.86b), the transition diagram has no diagonals and embeds onto a 2-cube. State assignment becomes simply $A=00, B=01, C=11, D=10$ (or similar Gray-code mapping).

Stage 4 — Excitation table. With the assignment fixed, write next-state codes $(Y_2 Y_1)$ for every (state, input) cell. K-map the columns to derive logic for $Y_1$ and $Y_2$. Output $z$ is a function of state alone (Moore), so it K-maps directly from the present-state bits.

The full pipeline summary:

What problem 9.34 specifically asks: walk through stages 1–4 above, preserving the Moore model throughout (so the merger constraint is "same output in stable cells", not the looser Mealy compatibility).