GO Classes DPP | TOC|FSM

Answer 1

1. Understanding the detection task

We're detecting the sequence $\mathbf{101}$:

• Moore machine: Output depends only on the current state.
  
  So when the sequence $\mathbf{101}$ ends at clock cycle $t$, the output $z=1$ occurs at cycle $t+1$ (because the state after receiving the last bit is the "detected 101" state, and output is associated with that state for the full cycle).
   
• Mealy machine: Output depends on current state and current input.
  
  So when the last bit (1) of 101 is read at cycle $t$, output $z=1$ occurs immediately at cycle $t$.

 

2. Input stream and detection times

Input:

$$
t_0: 0, ~t_1: 1, ~t_2: 0, ~t_3: 1, ~t_4: 0, ~t_5: 1, ~t_6: 0, ~t_7: 1
$$

Sequence $\mathbf{101}$ occurs ending at:
 

• $t_3$ (bits $t_1=1, ~t_2=0, ~t_3=1)$
   
• $t_5$ (bits $t_3=1, ~t_4=0, ~t_5=1)$
   
• $t_7$ (bits $t_5=1, ~t_6=0, ~t_7=1)$
   

At $t_3$ : input $=1$ completes $101 \rightarrow z=1$

At $t_5$ : input $=1$ completes $101 \rightarrow z=1$

At $t_7$ : input $=1$ completes $101 \rightarrow z=1$

Else $z=0$.
 

So Mealy output:

$$
t_0: 0, ~t_1: 0, ~t_2: 0, ~t_3: 1, ~t_4: 0, ~t_5: 1, ~t_6: 0, ~t_7: 1
$$

Detection at $t_3 \rightarrow$ output at $t_4$

Detection at $t_5 \rightarrow$ output at $t_6$

Detection at $t_7 \rightarrow$ output at $t_8$ (not in our range $t_0-t_7$, so ignore $t_8$ )

 

So Moore output:

$$
t_0: 0, ~t_1: 0, ~t_2: 0, ~t_3: 0, ~t_4: 1, ~t_5: 0, ~t_6: 1, ~t_7: 0
$$

Mealy: $0~0~0~1~0~1~0~1$

Moore: $0~0~0~0~1~0~1~0$


Observation: Mealy output is Moore output shifted left by $1$ cycle (with last bit different because Moore's last $1$ would be at $t_8$ ).

That matches option C: "The Mealy machine output leads the Moore machine output by $1$ cycle."