---
title: "DFA: even a and odd b"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:dfa-even-a-odd-b"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dfa-even-a-odd-b
site: BCT Engineering
---

# DFA: even a and odd b

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Chaitra
- Video: [Lec-13: DFA for Even a and Even b | Even a Odd b | Odd a and Even b | Odd a Odd b | TOC](https://www.youtube.com/watch?v=WKPeYsuBpm4) — Gate Smashers
- 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-a-odd-b
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Construct a DFA over {a, b} accepting strings having an even number of a's and an odd number of b's.

## Short answer

Use four states representing (a-count mod2, b-count mod2): q00 (even, even) start, q01 (even, odd) final, q10 (odd, even), q11 (odd, odd). On a, toggle first component; on b, toggle second. Accepts when state is q01.

## Answer

**Idea.** Remember only the parity of the number of a's and the parity of the number of b's. This gives 4 states: qᵢⱼ means (a-count mod 2 = i, b-count mod 2 = j).

M = (Q, {a, b}, δ, q00, {q01}) with Q = {q00, q01, q10, q11}.

#### Transition table
| State | a | b |
|---|---|---|
| → q00 | q10 | q01 |
| *q01 | q11 | q00 |
| q10 | q00 | q11 |
| q11 | q01 | q10 |

Reading a flips the first index, reading b flips the second. The final state is q01 (even a's, odd b's).

#### Diagram
```text
           a                  a
  ──►(q00) <──────────> (q10)
      ▲                    ▲
    b │                    │ b
      ▼                    ▼
    ((q01)) <──────────> (q11)
           a                  a
```

Every edge is two-way: a joins q00–q10 and q01–q11; b joins q00–q01 and q10–q11. Double circle = final state.

#### Test
- "aab": q00 →a q10 →a q00 →b q01, final, accepted (2 a's, 1 b).
- "ab": q00 → q10 → q11, not final, rejected (1 a).
- "b": q00 → q01, accepted.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does each state track?
   A. The last symbol read
   B. The number of symbols mod 4
   C. The length of the string
   D. The parities of the a-count and b-count
   Answer: D. q_ij: a mod 2 = i, b mod 2 = j, giving 4 states. (Key point: States)

2. Which state is final?
   A. q00
   B. q11
   C. q01 (even a, odd b)
   D. q10
   Answer: C. Even a's and odd b's gives q01. (Key point: Final state)

3. What does reading b do?
   A. Leaves the state unchanged
   B. Flips the a parity
   C. Resets to q00
   D. Flips the b parity (second index)
   Answer: D. a flips the first index, b flips the second. (Key point: Transition)

4. Is 'ab' accepted?
   A. Yes: it ends in q00
   B. Yes: it ends in q01
   C. No: it ends in q11
   D. No: it ends in q00
   Answer: C. ab has 1 a (odd), so it is rejected. (Key point: Test)

## Related in Theory of Computation

- [RE: even a's followed by odd b's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-even-a-odd-b) — Theory of Computation, chapter 2
- [DFA: even 0s and even 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-zeros-even-ones) — Theory of Computation, chapter 2
- [DFA for {00}*{11}* language](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-00-star-11-star) — Theory of Computation, chapter 2
- [DFA starts or ends with 01](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-starts-or-ends-01) — Theory of Computation, chapter 2
- [Convert ε-NFA (q0..q4) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-epsilon-q4) — Theory of Computation, chapter 2, asked 2×
- [Convert NFA (q0..q4, 0/1) to DFA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anfa-to-dfa-five-states) — Theory of Computation, chapter 2, asked 2×

## Related in other subjects

- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×
- [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×
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2