---
title: "Design FSA accepting even number of a's"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsa-even-number-of-a"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-even-number-of-a
site: BCT Engineering
---

# Design FSA accepting even number of a's

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2072 Asoj, 6 marks; 2069 Bhadra, 6 marks (asked 2 times)
- 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_4/discrete_structure/fsa-even-number-of-a
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Design a Finite State Automata that accepts precisely those strings over {a, b} that contain an even number of a's. Your design should include the proper definition of the finite-state automata, transition table and the transition diagram.

## Short answer

The DFA has states q0 (even a's, start and final) and q1 (odd). On 'a', toggle state; on 'b' remain. Transition table: q0 –a→ q1, –b→ q0; q1 –a→ q0, –b→ q1. It accepts strings over {a,b} with an even number of a's.

## Answer

#### Idea
We only need to remember whether the number of a's read so far is even or odd. So two states are enough: q0 (even number of a's, including zero) and q1 (odd number). Reading a toggles the state; reading b does not change it.

#### Formal definition
M = (Q, Σ, δ, q0, F) where
- Q = {q0, q1}
- Σ = {a, b}
- Start state q0
- F = {q0} (final state, since the empty string has zero a's, which is even)
- δ is given by the table below.

#### Transition table
| State | a | b |
|---|---|---|
| → *q0 | q1 | q0 |
| q1 | q0 | q1 |

(→ start state, * final state)

#### Transition diagram
```text
          b                      b
         ┌─┐                    ┌─┐
         ↓ │                    ↓ │
  ──→ (( q0 )) ───────a──────→ ( q1 )
            ↑                     │
            └──────────a──────────┘
```

#### Trace
- "abab": q0 –a→ q1 –b→ q1 –a→ q0 –b→ q0. Ends in q0, accepted (2 a's).
- "baab": q0 –b→ q0 –a→ q1 –a→ q0 –b→ q0, accepted.
- "ab": q0 –a→ q1 –b→ q1, rejected (1 a).

The language is L = {w ∈ {a, b}* : number of a's in w is even} = b*(ab*ab*)*. I verified the machine against the count of a's for all strings up to length 8.

## Check yourself

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

1. What do the two states remember?
   A. The last symbol read
   B. Whether the number of a's read is even or odd
   C. The length of the string
   D. The number of b's
   Answer: B. q0 = even a's, q1 = odd a's. (Key point: State meaning)

2. What does reading b do?
   A. Toggles the state
   B. Stays in the same state
   C. Goes to q0
   D. Rejects
   Answer: B. Only a toggles the state. (Key point: Transitions)

3. Why is q0 final?
   A. It is the start state only
   B. Zero a's (the empty string) is an even count
   C. It has no transitions
   D. It is reached after b
   Answer: B. Even count includes zero, and q0 represents even. (Key point: Final state)

4. Where does 'ab' end, and is it accepted?
   A. q0, accepted
   B. q1, rejected
   C. q1, accepted
   D. q0, rejected
   Answer: B. One a leaves the machine in q1, which is not final. (Key point: Trace)

## Close variants set in other exams

- [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×
- [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4×

## Related in Discrete Structure

- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2