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

# Design FSA accepting odd number of b's

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2071 Bhadra, 6 marks
- 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-odd-number-of-b
- 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 odd number of b's. Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram.

## Short answer

The DFA has states E (even, start) and O (odd, final). On a, stay in current state; on b, switch state. It accepts exactly strings with an odd number of b's.

## Answer

#### Idea
Track the parity of the number of b's read. State E: even number of b's (start). State O: odd number of b's (final). Reading b switches state; reading a keeps it.

#### Formal definition
M = (Q, Σ, δ, q₀, F) where Q = {E, O}, Σ = {a, b}, q₀ = E, F = {O}, and δ is:

#### Transition table
| State | a | b |
|---|---|---|
| → E | E | O |
| *O | O | E |

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

#### Trace
- "abb": E –a→ E –b→ O –b→ E. Rejected (2 b's).
- "bab": E –b→ O –a→ O –b→ E. Rejected.
- "aabbb": E –a→ E –a→ E –b→ O –b→ E –b→ O. Accepted (3 b's).

The language is L = {w ∈ {a, b}* : number of b's is odd} = a*b a*(b a*b a*)*. I verified the machine against the b-count 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 of the odd-b automaton remember?
   A. The last symbol read
   B. The total number of a's read
   C. The parity (even or odd) of the number of b's read so far
   D. Whether the string started with b
   Answer: C. Only parity matters for deciding odd versus even b's. (Key point: State meaning)

2. Which transitions does the machine use?
   A. Reading a switches state; b stays
   B. Both a and b switch state
   C. Both a and b stay in the same state
   D. Reading b switches between E and O; reading a stays in the same state
   Answer: D. Only a b changes the parity of the b-count, a does not. (Key point: Transitions)

3. Which state is final, and why?
   A. O, because it means an odd number of b's
   B. E, because it is the start state
   C. Both E and O
   D. Neither; the machine uses a dead state
   Answer: A. Strings with an odd number of b's must end in the odd state O. (Key point: Final state)

4. What happens for the input aabbb?
   A. It ends in E and is rejected
   B. It ends in O and is accepted (3 b's)
   C. It ends in O and is rejected
   D. It enters a dead state
   Answer: B. E→E→E→O→E→O: three b's is odd, so accepted. (Key point: Trace)

## Close variants set in other exams

- [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×
- [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