Exercises — State diagram and state table design

The output appears on the arrows (input/output), not inside the bubbles. Output depends on state and current input → this is a Mealy machine. Rule: X/Z on arrows ⇒ Mealy. Sᵢ/Z inside bubbles ⇒ Moore.

The proper prefixes of 110 are: "" (nothing), 1, 11. Detecting the full 110 produces the output but does not add a resting prefix beyond those. So we need $S_0$ (nothing), $S_1$ (1), $S_2$ (11) → 3 prefix-states for a Mealy detector.

101 + 1 = 1011 → MATCH, so $Z=1$. Because overlap is allowed, the trailing 1 is a fresh prefix, so we land in $S_1$. Answer: Next $=S_1$, $Z=1$.

Start $S_0$.

• 1 → $S_1$ / 0
• 0 → $S_2$ / 0
• 1 → $S_3$ / 0
• 1 → $S_1$ / 1 ← match #1 (1011)
• 0 → $S_2$ / 0
• 1 → $S_3$ / 0
• 1 → $S_1$ / 1 ← match #2 (overlap, 1011)

Two matches. The overlap works because after match #1 we sat in $S_1$ (holding a 1), letting 011 complete a new 1011.

Prefix-states: $S_0$ (nothing / matched a useless bit), $S_1$ (matched 0).

Overlap note: after matching 01, the trailing 1 is not a prefix of 01, so we correctly go to $S_0$.

The missing cell is $S_0$ on input $X=1$. A lone 1 matches no prefix of 01, so we stay in $S_0$ with $Z=0$. Answer: $S_0$ / 0. A state table must give a next-state entry for every (state, input) pair.

Wrong rule: after a match, jump to $S_0$.

• 1→$S_1$ · 0→$S_2$ · 1→$S_3$ · 1→ MATCH #1, then wrongly →$S_0$
• 0→$S_0$ · 1→$S_1$ · 1→$S_1$

Ends in $S_1$ with only 1 match. The correct machine (parent) reports 2 matches on the same string. So resetting to $S_0$ discards the trailing 1 and misses the overlapping 1011. Principle: after a match, jump to the state for the longest suffix of the pattern that is also a prefix of it — for 1011 that suffix is 1 → $S_1$.

After matching 1010, look at its suffixes and ask which is also a prefix of 1010:

• suffix 0 → prefix? 1010 starts with 1, not 0. No.
• suffix 10 → prefix? 1010 starts with 10. Yes.
• suffix 010, 1010 → longer, check biggest first: 010? starts with 0? no. 1010 full? that's the whole match, not a proper overlap.

Longest suffix that is also a prefix = 10 → jump to ==$S_2$==.

Moore must arrive in a state to show $Z=1$. So add accept state $S_2$ (01 matched, output 1).

$S_2$ behaves for future input exactly like $S_0$ after a 1 (its trailing 1 matches no prefix), but it displays output 1. Count: Mealy = 2 states, Moore = 3 states → Moore needed one more.

(a) Mealy — reason each cell:

Overlap check: after matching 110, its suffixes 0,10 are not prefixes of 110, so we go to $S_0$. Correct.

(b) Moore — add accept state $S_3$ ($Z=1$), reached when $S_2$ sees a 0:

• 1→$S_1$/0
• 1→$S_2$/0
• 0→$S_0$/1 ← match #1 (110)
• 1→$S_1$/0
• 1→$S_2$/0
• 0→$S_0$/1 ← match #2 (110)
• 0→$S_0$/0

Two matches. (No overlap possible here since 110 has no suffix that is also a prefix, so back-to-back 110110 gives two clean matches.)

The prefix-states are the proper prefixes of the pattern: "", then the first 1 bit, first 2 bits, …, first $n-1$ bits. That is exactly $n$ states for a Mealy detector (states $S_0\dots S_{n-1}$), regardless of pattern. So a length-3 pattern needs 3 Mealy states (e.g. 110 from L4.1: $S_0,S_1,S_2$). Moore adds one accept state to display the output → 4 Moore states for a length-3 detector. General rule: Mealy needs $n$ states; Moore needs $n+1$ (an accept state), confirming the parent's "Moore needs ≥ as many states as Mealy" trade-off. Here Moore uses exactly one extra.

States: $S_0=$"", $S_1=$"1", $S_2=$"10", $S_3=$"101".

Trace 1010100 from $S_0$:

• 1→$S_1$/0
• 0→$S_2$/0
• 1→$S_3$/0
• 0→$S_2$/1 ← match #1 (1010)
• 1→$S_3$/0
• 0→$S_2$/1 ← match #2 (overlapping 1010, sharing the middle 10)
• 0→$S_0$/0

Two matches — and the second is a genuine overlap, only possible because we jumped to $S_2$ (not $S_0$) after the first match. See the trace figure.

Buggy rule: after 1010 match, go to $S_0$.

• 1→$S_1$ · 0→$S_2$ · 1→$S_3$ · 0→ MATCH #1, then wrongly →$S_0$
• 1→$S_1$ · 0→$S_2$ · 0→$S_0$

Ends with only 1 match. It loses the second, overlapping 1010 (positions 3–6 of the string), because throwing away the shared middle 10 destroys the overlap. The correct machine (L5.2) finds 2.

The longest suffix of the pattern that is also a prefix of the pattern.

$n$ overlapping detector? Mealy needs $n$ states; Moore needs $n+1$ (an extra accept state to display the output).

Every (present-state, input) pair has a defined next-state (and output) entry.