Moore machine ($s^{+}=F(s,a),z=G(s)$)

A Moore machine is a finite-state machine whose output depends only on the current state. In a clocked implementation, a state entered at a clock edge determines the following period's output. Specifying an initial state is necessary to define startup behavior.

A synchronous sequential circuit can use three states: armed, pulse, and waiting. Only the pulse state has output one. A reset input rearms the circuit, including when it arrives during the pulse cycle; this permits pulses on alternate clock cycles while each pulse still lasts exactly one cycle.

Enter a distinguished Moore machine state whose output is active, and ensure that every outgoing transition leaves that state for an inactive-output state. The output then lasts one clock period. Its outgoing transitions may simultaneously recognize the start of the next event, avoiding an unnecessary idle cycle. The one-period statement refers to the synchronous logical model, with ordinary propagation delay after each clock edge.

For a fixed word $w$, store the length of the longest suffix of the received stream that is also a prefix of $w$. On a new input symbol, append it to the represented prefix and select the longest resulting suffix that is a prefix of $w$. The complete-word state signals recognition. Its outgoing transitions retain proper suffix matches, allowing overlapping occurrences rather than automatically restarting from the empty prefix. This is the finite-state form of the prefix information used by the Knuth-Morris-Pratt algorithm.

For example, recognizing $1101$ needs suffix-prefix states of lengths zero through four. After a complete match followed by one, the last two symbols are $11$, so the next state retains length two. This permits the second match in $1101101$ without clearing the useful suffix.