Design a Finite State Machine or Abstract Model for a Parity Checker

A parity checker is a finite-state device that processes a bit stream and decides whether the number of 1s seen so far is even or odd. Because parity alternates each time a 1 arrives, the checker needs only two memory states: one representing “even number of 1s so far” and one representing “odd number of 1s so far.” This is a standard example of a DFA recognizing the parity language. In automata-theory terms, we maintain a state that captures the parity of the prefix; acceptance depends on the final state. 2

Key modeling choices

• DFA / abstract automaton: no outputs during reading; “accept/reject” at the end.
• Moore FSM (output = state): output is pinned to the current state.
• Mealy FSM (output = transition): output can depend on current input and current state.

Mermaid view of the core two-state parity memory (abstract DFA concept):

Footnotes

1. Finite-state machine - MTSU course notes (Parity checker description) - Explains parity checker as counting 1s in a bit-serial input stream and distinguishes odd/even parity behavior. ↩

2. Lecture 3 - Finite Automata (Parity using 2 states) - Provides a formal DFA construction for odd parity with two states representing parity so far. ↩

3. Mealy vs Moore machine explanation (output depends on state vs state+input) - Describes the distinction: Moore output depends only on present state; Mealy output depends on state and current input. ↩

Core keywords (mental model)

• Parity
• DFA
• Moore machine
• Mealy machine
• Transition function

1) Abstract model as a DFA (accept at the end)

Language definition

A common parity task is: accept a binary string if it contains an odd number of 1s (odd-parity language). This can be implemented by a DFA with exactly two states tracking the parity of the number of 1s read so far.

DFA definition

Let $M=(Q,\Sigma,\delta,q_0,F)$.

• DFA
• $Q=\{E,O\}$ where:
  • $E$: “even number of 1s so far”
  • $O$: “odd number of 1s so far”
• $\Sigma=\{0,1\}$
• $q_0=E$ (empty prefix has 0 ones → even)
• For odd parity acceptance, $F=\{O\}$.

Transition function (parity flip rule)

The parity state changes only when the next input symbol is 1:

• $\delta(E,0)=E$
• $\delta(E,1)=O$
• $\delta(O,0)=O$
• $\delta(O,1)=E$

This aligns with standard parity-checker DFA construction: two states represent parity of what has been seen so far, start at even, and accept the odd-parity state. 2

DFA transition table

Mermaid for the DFA structure:

Footnotes

1. Lecture 3 - Finite Automata (Parity using 2 states) - Provides a formal DFA construction for odd parity with two states representing parity so far. ↩ ↩²

2. Finite State Machine Design Procedure (Parity checker example, Moore/Mealy context) - Includes an odd parity checker example and discusses Moore/Mealy forms and transition/output relationships. ↩

2) Moore FSM design (output depends only on state)

When you want the machine to produce an output continuously (at clock edges) indicating whether the current prefix has even/odd parity, a Moore machine is natural: the output is a function of the current state only.

Moore specification

• States: $E$ and $O$
• Output in each state:
  • For an odd-parity checker output=1 iff odd, set:
    • $y(E)=0$
    • $y(O)=1$
• Transitions: same toggling rule as DFA.

This corresponds to the Moore convention that output is associated with the state (not the transition).

Moore state table

Note: On a clock where the input causes a transition (e.g., $E \xrightarrow{1} O$), a Moore output convention typically reflects the state after the clock edge (implementation detail), because Moore outputs are tied to state.

Footnotes

1. Mealy vs Moore machine explanation (output depends on state vs state+input) - Describes the distinction: Moore output depends only on present state; Mealy output depends on state and current input. ↩ ↩² ↩³

3) Mealy FSM design (output depends on state + input)

If you want the output to respond as soon as the input symbol is applied (potentially one-cycle earlier in synchronous implementations), a Mealy machine can be used: output depends on both current state and current input.

Mealy specification

Define output $y=g(S, x)$. For an odd-parity checker output=1 iff odd after consuming the current input symbol, you can set:

• From $E$:
  • input 0 keeps even → output 0
  • input 1 makes odd → output 1
• From $O$:
  • input 0 keeps odd → output 1
  • input 1 makes even → output 0

So the Mealy output mapping is:

• $y(E,0)=0$, $y(E,1)=1$
• $y(O,0)=1$, $y(O,1)=0$

And the next-state mapping remains:

• $\delta(E,0)=E,\ \delta(E,1)=O$
• $\delta(O,0)=O,\ \delta(O,1)=E$

This matches the defining distinction: Moore output depends only on state, while Mealy output depends on state and input.

Mealy state-transition/output table

Footnotes

1. Mealy vs Moore machine explanation (output depends on state vs state+input) - Describes the distinction: Moore output depends only on present state; Mealy output depends on state and current input. ↩ ↩²