Answer

Parity Checker FSM: Checks if number of 1s in input is even (even parity) or odd (odd parity). Common use: error detection in communication.

Assumptions

• Input alphabet: $\Sigma = \{0, 1\}$ (binary stream)
• Output: Even (0) or Odd (1) parity bit after each input, or final parity at end
• We present Moore and Mealy versions

---

1. Moore Machine (Output on State)

States: $Q = \{E, O\}$

• $E$: Even number of 1's seen so far (initial, accepting for even parity)
• $O$: Odd number of 1's seen so far

Output function $\lambda$:

• $\lambda(E) = 0$ (even parity)
• $\lambda(O) = 1$ (odd parity)

Transition function $\delta$:

State	Input 0	Input 1
$E$	$E$	$O$
$O$	$O$	$E$

State Diagram:

        0
     ┌────┐
     │    ▼
  (E)───►(O)
     ▲   │
     └───1

• On 0: stay in same parity state
• On 1: flip parity

Formal Moore: $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$

• $Q = \{E, O\}$, $\Sigma = \{0,1\}$, $\Delta = \{0,1\}$
• $\delta(E,0)=E, \delta(E,1)=O, \delta(O,0)=O, \delta(O,1)=E$
• $\lambda(E)=0, \lambda(O)=1$
• $q_0 = E$

---

2. Mealy Machine (Output on Transition)

States: $Q = \{E, O\}$ (same states, no output on states)

Output on transition:

Transition	Input	Next State	Output
$E \xrightarrow{0} E$	0	$E$	0
$E \xrightarrow{1} O$	1	$O$	1
$O \xrightarrow{0} O$	0	$O$	1
$O \xrightarrow{1} E$	1	$E$	0

State Diagram:

      0/0
   ┌─────┐
   │     ▼
  (E)──►(O)
  │1/1   │0/1
   └─────1/0

Formal Mealy: $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$ with $\lambda: Q\times\Sigma \to \Delta$.

---

3. Even Parity Generator (Output at End)

If only final parity needed (not running):

• Run Moore/Mealy above
• After last input, output $\lambda(q)$ (Moore) or last transition output (Mealy)
• Even parity = 0 if even # of 1's, 1 if odd

Test Sequence

Input	Moore State Seq	Moore Output Seq	Mealy Output Seq
1011	$E \to O \to O \to E \to O$	0,1,1,1,0	1,1,1,0
Even # 1s: 1100 → ends in E, output 0
Odd # 1s: 110 → ends in O, output 1

---

Final Answer

Parity Checker FSM — 2-state Moore/Mealy machine tracking even/odd count of 1's.

• Moore: Output = state parity (E→0, O→1)
• Mealy: Output on each transition (flip on 1, hold on 0)
• Transitions: 0 = stay, 1 = flip
• Minimal: 2 states (even/odd are distinguishable)