DFA Construction for Even # of 0s and Odd # of 1s over $\{0,1\}$

We want a deterministic finite automaton (DFA) over $\Sigma=\{0,1\}$ that accepts exactly those strings that contain:

• an even number of 0s, and
• an odd number of 1s.

A standard approach is to build a product-parity automaton that tracks two parities simultaneously: parity of the number of 0s, and parity of the number of 1s.

We represent each state as a pair: $\text{state} = (p_0, p_1)$ where $p_0\in\{\text{even},\text{odd}\}$ is the parity of the number of 0s read so far, and $p_1\in\{\text{even},\text{odd}\}$ is the parity of the number of 1s read so far. The DFA starts at $(\text{even},\text{even})$ because the empty string has 0 zeros (even) and 0 ones (even). It accepts when $(p_0,p_1)=(\text{even},\text{odd})$.

Mermaid view of the core idea:

Key terms:

• DFA
• Alphabet
• Accepting state
• Transition function

DFA definition (explicit construction)

We define the DFA $M=(Q,\Sigma,\delta,q_0,F)$ as follows.

• State set:
  $Q=\{q_{ee}, q_{eo}, q_{oe}, q_{oo}\}$ where $q_{ab}$ means:

  • $a$ = parity of # of 0s so far (e=even, o=odd)
  • $b$ = parity of # of 1s so far (e=even, o=odd)

• Alphabet:
  $\Sigma=\{0,1\}$

• Start state:
  $q_0=q_{ee}$

• Accepting set:
  $F=\{q_{eo}\}$
  because we need even number of 0s and odd number of 1s.

• Transition function:
  Reading a symbol flips the parity of the corresponding count:

  • On input $0$: toggle parity of # of 0s, leave # of 1s parity unchanged.
  • On input $1$: toggle parity of # of 1s, leave # of 0s parity unchanged.

Transition table

Let $\delta(q,s)$ be the next state.

This follows directly from parity toggling:

• $0$ flips “#0s parity”
• $1$ flips “#1s parity”

Verification: trace accepted vs. rejected strings

We verify using representative strings by counting 0s and 1s and/or simulating the DFA by state transitions.

Strings that should be accepted (even #0s, odd #1s)

We must have:

• #0s = even (0,2,4,...)
• #1s = odd (1,3,5,...)

1. Input: 1

• #0s = 0 (even), #1s = 1 (odd) → accept
• DFA trace:
  $q_{ee} \xrightarrow{1} q_{eo}$ (accepting)

2. Input: 001

• #0s = 2 (even), #1s = 1 (odd) → accept
• DFA trace:
  $q_{ee}\xrightarrow{0}q_{oe}\xrightarrow{0}q_{ee}\xrightarrow{1}q_{eo}$ (accept)

3. Input: 10101

• #0s = 2 (even), #1s = 3 (odd) → accept

4. Input: 000111

• #0s = 3 (odd) actually this one would be rejected (included here as a contrast).
  So we instead use: Input: 00111
  • #0s = 2 (even), #1s = 3 (odd) → accept

Strings that should be rejected (violates at least one parity condition)

1. Input: 0

• #0s = 1 (odd), #1s = 0 (even) → reject
• DFA trace:
  $q_{ee}\xrightarrow{0}q_{oe}$ (not accepting)

2. Input: 11

• #0s = 0 (even), #1s = 2 (even) → reject
• DFA trace:
  $q_{ee}\xrightarrow{1}q_{eo}\xrightarrow{1}q_{ee}$ (back to non-accepting)

3. Input: 010

• #0s = 2 (even), #1s = 1 (odd) → actually accept (use as a positive check)
• Therefore for rejection use 0110:
  • 0110 has #0s=2 (even), #1s=2 (even) → reject

4. Input: empty string ε

• #0s=0 (even), #1s=0 (even) → needs odd #1s, so reject
• DFA trace: start at $q_{ee}$ which is non-accepting.

Quick state interpretation example

Consider input 001:

• Start: $q_{ee}$.
• Read 0: $q_{ee}\to q_{oe}$ (odd zeros, even ones).
• Read 0: $q_{oe}\to q_{ee}$ (even zeros, even ones).
• Read 1: $q_{ee}\to q_{eo}$ (even zeros, odd ones) → accept.

This demonstrates the DFA’s correctness mechanism: it never “counts” unboundedly; it only tracks parity.