--- title: "DFA: even 0s and even 1s" subject: "Theory of Computation" chapter: 2 key: "semester_3/theory_of_computation:dfa-even-zeros-even-ones" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-even-zeros-even-ones site: BCT Engineering --- # DFA: even 0s and even 1s Theory of Computation · Chapter 2: Finite Automata - Asked in: 2070 Chaitra - Video: [Theory of Computation: Example for DFA (Even 0's and even 1's)](https://www.youtube.com/watch?v=wK-qsHg-4qI) — Anita R - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-even-zeros-even-ones - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2 ## Question Design a DFA for L = {x ∈ {0,1}* : x has an even number of 0's and an even number of 1's}. ## Short answer DFA with four states tracking parity mod 2 of 0's and 1's: q00 (even, even) start and accepting. Transitions: 0 flips first index, 1 flips second. 0110 returns to q00 (accepted); 010 ends in q01 (rejected). ## Answer **Idea.** Track the parity of 0's and 1's. Four states qᵢⱼ: i = number of 0's mod 2, j = number of 1's mod 2. The start state q00 is also the only final state (even, even; ε is accepted). M = ({q00, q01, q10, q11}, {0, 1}, δ, q00, {q00}) | State | 0 | 1 | |---|---|---| | → *q00 | q10 | q01 | | q01 | q11 | q00 | | q10 | q00 | q11 | | q11 | q01 | q10 | ```text 0 0 ──►((q00)) <──────────> (q10) ▲ ▲ 1 │ │ 1 ▼ ▼ (q01) <──────────> (q11) 0 0 ``` Each edge is two-way: 0 joins q00–q10 and q01–q11; 1 joins q00–q01 and q10–q11. #### Test - "0110": q00 →0 q10 →1 q11 →1 q10 →0 q00. Accepted. - "010": q00 → q10 → q11 → q01. Rejected (two 0's, one 1). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does q_ij record? A. i = 0s mod 2, j = 1s mod 2 B. Number of 0s and 1s exactly C. Length mod 2 D. Last two symbols Answer: A. Only parities are needed. (Key point: State meaning) 2. Why is q00 start and final? A. To reject ε B. Because the DFA has one state C. Because all strings are accepted D. ε has zero 0s and zero 1s, both even Answer: D. ε belongs to L. (Key point: Final state) 3. What is the end state for 010? A. q10 B. q00 C. q01, not final D. q11 Answer: C. Two 0s even, one 1 odd. (Key point: Test) ## Related in Theory of Computation - [DFA: even a and odd b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-a-odd-b) — Theory of Computation, chapter 2 - [Pumping lemma: equal 0s and 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-equal-zeros-ones) — Theory of Computation, chapter 2, asked 2× - [Configuration of DFA; DFA with 01 and 10](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-config-01-and-10) — Theory of Computation, chapter 2 - [Convert NFA (q0,q1,q2) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-01-q0q2) — Theory of Computation, chapter 2 - [DFA for (a(ab)*b)*](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-re-a-ab-star-b) — Theory of Computation, chapter 2 - [DFA avoiding substring 10110](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-not-substring-10110) — Theory of Computation, chapter 2 ## Related in other subjects - [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4× - [Handshaking theorem; even number of odd vertices](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-even-odd-degree-proof) — Discrete Structure, chapter 4, asked 3× - [Count number of 0s in ROM data](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3A8051-count-zeros-asm) — Embedded System, chapter 9, asked 2× - [Count number of 1s in ROM data](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3A8051-count-ones-asm) — Embedded System, chapter 9, asked 2×