Design and Equivalence of Mealy/Moore Machines Detecting the Overlapping Sequence 1010

We want a sequential circuit that reads a binary stream $x \in \{0,1\}^\*$ and outputs $1$ exactly when the last four input bits form the pattern 1010, with overlapping allowed (so a new detection can begin before the previous one “finishes”). This is a classic sequence detector design problem using finite-state machines.

We will build:

1. a Moore machine (output depends only on state) for 1010 with overlapping,
2. a Mealy machine directly,
3. then convert the Moore machine into an equivalent Mealy machine and prove equivalence.

Key automata notions used below:

• Moore machine
• Mealy machine
• overlapping detection
• equivalence of FSMs.

We will use the standard Moore→Mealy edge-labeling rule: move each Moore state's output onto the incoming transitions of the corresponding state in the Mealy model.2

Footnotes

1. Finite-state machine - Wikipedia - Describes Moore→Mealy conversion by putting destination Moore state output on Mealy transitions. ↩

2. Moore to Mealy Machine Conversion - Tutorialspoint - Provides conversion rules moving state outputs to incoming Mealy transitions and notes about equivalence. ↩

Strategy: represent “how much of 1010 we have matched so far”

Define machine states to represent the length of the longest suffix of the processed input that is also a prefix of the target pattern 1010.

Let the target be $P = 1010$. Its proper prefixes are:

• $\epsilon$ (length 0),
• 1 (length 1),
• 10 (length 2),
• 101 (length 3),
• 1010 (length 4).

In a suffix-tracking design, after each new input bit, we update to the longest prefix that matches the new suffix—this naturally supports overlapping.

Moore machine for detecting overlapping 1010

Moore transition table

Let Moore output be $Z(s)$ (only depends on current state). States:

• $S_0$: matched length 0 (no useful suffix),
• $S_1$: matched 1,
• $S_2$: matched 10,
• $S_3$: matched 101,
• $S_4$: matched 1010 (detection state).

Moore outputs:

• $Z(S_4)=1$,
• $Z(S_0)=Z(S_1)=Z(S_2)=Z(S_3)=0$.

Now compute transitions by longest suffix that is also a prefix of 1010.

Reasoning highlights (overlap):

• From $S_3$ on input 0, we complete 1010, so go to $S_4$.
• From $S_4$ on input 0, the last two bits are 10, so we land in $S_2`.
• From $S_4$ on input 1, the last bit is 1, so we land in $S_1$.

Mermaid diagram (Moore)

Mealy machine for detecting overlapping 1010 (output on transitions)

For a Mealy machine, the output $Y$ is associated with the transition labeled by the input.

We can obtain a compact Mealy detector by emitting $Y=1$ on the transition that completes 1010.

Define Mealy states to be the same matched-prefix states $S_0$–$S_3$ (no need to keep an “$S_4$ state” because detection is produced on the edge). However, we must still transition correctly after detection for overlap.

Let $Y(s,b)=1$ iff from state $S_3we read input0(because that edge completes1010`).

Mealy transition/output table

Notes:

• From $S_3` on input `0`, we detect `1010`, and after consuming that `0`, the longest suffix that's also a prefix is `10`, i.e., next state$S_2$—this is exactly the overlap behavior.

Mermaid diagram (Mealy)

Converting the Moore machine into an equivalent Mealy machine

Conversion rule (standard):

• In a Moore machine, output is on the state.
• Convert to an equivalent Mealy machine by transferring that state’s output onto each incoming transition to that state.2

So, for every Moore transition $s \\xrightarrow{b} s'$, label the Mealy transition with output $Z(s')$.

This yields a Mealy machine whose output timing matches the Moore machine one step “earlier” in the transition-label representation; equivalence is stated in terms of the output sequence produced for the same input stream (after appropriate alignment of Moore’s state-output convention).

Footnotes

1. Finite-state machine - Wikipedia - Describes Moore→Mealy conversion by putting destination Moore state output on Mealy transitions. ↩ ↩²

2. Moore to Mealy Machine Conversion - Tutorialspoint - Provides conversion rules moving state outputs to incoming Mealy transitions and notes about equivalence. ↩

Resulting Mealy transitions from the Moore machine

Using $Y = Z(\\text{next state})$, only transitions that enter $S_4$ produce output $1$.

From the Moore transition table:

• The only way to enter $S_4$ is from $S_3$ on input 0.
• Therefore, the converted Mealy machine labels exactly that transition with output $1$.

If we now drop $S_4$ as a “stabilizing” Moore state (while preserving next-state behavior), the converted Mealy machine coincides with the direct Mealy detector earlier.

Concretely, in the converted Mealy machine:

• $Y(S_3,0)=Z(S_4)=1$,
• all other $Y(s,b)=0$.

This matches the Mealy table:

• From $S_3$ on 0, go to $S_2$ with output $1`,
• Otherwise output $0$.

Proof of equivalence (Moore → Mealy conversion correctness)

We prove that the Moore machine $M_{\\text{Moore}}$ and its converted Mealy machine $M_{\\text{Mealy}}$ produce the same output stream for every input sequence.

Formal definitions (output interpretation)

Let:

• Moore machine output is $Z(s_t)$ where $s_t$ is the state during the $t$-th input step.
• Mealy machine output is labeled on transitions: if the machine is in $s_t$ and reads input $b_t$, it outputs $Y_t = Y(s_t,b_t)$ on the transition to $s_{t+1}$.

Using the conversion rule, we set:

$$Y(s,b) = Z(\\delta(s,b)).$$

This matches the standard Moore→Mealy conversion by placing the destination Moore state’s output on the transition. The correctness argument follows by induction on input length.2

Theorem

For any input string $b_0 b_1 \\cdots b_{n-1}$, the Mealy output on transition $t$ equals the Moore output of the destination state at time $t+1$:

$$Y_t = Z(s_{t+1}).$$

Thus, the output sequences align exactly with the intended timing of “output from states” being transferred onto the transition edges.

Proof (by induction)

Base case ($t=0$):
Moore: after applying input $b_0$, the next state is $s_1 = \\delta(s_0,b_0)$, and the Moore output associated with being in $s_1$ is $Z(s_1)$.
Mealy: by construction, the output on the transition reading $b_0$ is

$$Y_0 = Y(s_0,b_0) = Z(\\delta(s_0,b_0)) = Z(s_1).$$

So the equality holds.

Inductive step: Assume for some $t \\ge 0$ that

$$Y_t = Z(s_{t+1}).$$

Consider transition at time $t+1$. In both machines, the state before reading input $b_{t+1}$ is the same reachable state (call it $s_{t+1}$). The Moore next state is $s_{t+2}=\\delta(s_{t+1},b_{t+1})$.
Mealy outputs

$$Y_{t+1} = Y(s_{t+1},b_{t+1}) = Z(\\delta(s_{t+1},b_{t+1})) = Z(s_{t+2}).$$

So the equality also holds at $t+1$.

By induction, the output alignment holds for all $t$, hence the machines are equivalent under the conversion mapping. 

Footnotes

1. Finite-state machine - Wikipedia - Describes Moore→Mealy conversion by putting destination Moore state output on Mealy transitions. ↩

2. Moore to Mealy Machine Conversion - Tutorialspoint - Provides conversion rules moving state outputs to incoming Mealy transitions and notes about equivalence. ↩

Comparison: Moore vs Mealy for this detector