Consider the language $L = \{0^i 1^j \mid i + j \text{ is even}\}$. Is this language regular?

1. Key insight: $i + j$ is the TOTAL number of symbols. We don't need to know $i$ and $j$ separately — only the parity of their sum. 2. Parity of a count over $\{0, 1\}^*$ is recognisable by a 2-state DFA: state 0 (even count so far, ACCEPTING), state 1 (odd count, rejecting). Each symbol flips state. 3. But wait — the language requires the string to be of the form $0^* 1^*$ (zeros then ones). We need to enforce that ordering AS WELL as the parity. 4. Solution: a 4-state DFA. Two 'modes' (reading 0's, reading 1's), each with two parity sub-states. Track which mode we're in via the transition graph. 5. Since this DFA exists, $L$ is regular — option A. 6. Option B confuses this with $\{0^n 1^n\}$ (which is non-regular). Option C is unnecessary. Option D conflates with decision problems. _Source: Jeff Erickson, "Models of Computation", §2.4 (DFA construction examples)._