---
title: "Regular expression and FSA: at least three b's"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsa-at-least-three-b"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-at-least-three-b
site: BCT Engineering
---

# Regular expression and FSA: at least three b's

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2074 Bhadra, 2+6 marks
- Video: [Lec-29: Regular Expressions in TOC with examples | Formal Definition](https://www.youtube.com/watch?v=rjG5LwbqAp4) — 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-at-least-three-b
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Given a language, L = {w ∈ {a, b}* : w contain at-least three 'b' s}. Write the regular expression for L and design a Finite State Automata that accepts the Language L. Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram.

## Short answer

Regular expression: a*ba*ba*b(a+b)*. DFA uses states q0 to q3 counting b seen (0 to ≥3). On a, loop; on b, advance until q3, which is final and loops on a and b.

## Answer

L = {w ∈ {a, b}* : w contains at least three b's}.

#### Regular expression
**a\*ba\*ba\*b(a + b)\***

The three b's are separated by any number of a's, and after the third b any string is allowed.

#### Idea for the automaton
Count the b's seen so far, stopping at 3: q0 (no b), q1 (one b), q2 (two b's), q3 (three or more b's, final). The symbol a never changes the count. Once in q3 we stay there.

#### Formal definition
M = (Q, Σ, δ, q0, F): Q = {q0, q1, q2, q3}, Σ = {a, b}, start state q0, F = {q3}, δ as in the table.

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

#### Transition diagram
```text
   a        a        a         a, b
  ┌─┐      ┌─┐      ┌─┐       ┌─┐
  ↓ │      ↓ │      ↓ │       ↓ │
→(q0)─b──→(q1)─b──→(q2)─b──→((q3))
```

#### Trace
- "abab": q0 –a→ q0 –b→ q1 –a→ q1 –b→ q2. Ends in q2, rejected (2 b's).
- "babab": q0 –b→ q1 –a→ q1 –b→ q2 –a→ q2 –b→ q3. Accepted.

I checked both the machine and the regular expression against the b-count for all strings up to length 8; they agree.

## Check yourself

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

1. Which regular expression describes strings with at least three b's?
   A. a*ba*ba*b
   B. (a+b)*bbb
   C. (ba*)^3
   D. a*ba*ba*b(a+b)*
   Answer: D. Three b's separated by any a's, then anything is allowed after the third b. (Key point: Regular expression)

2. What do q0, q1, q2, q3 represent?
   A. Number of b's seen so far: 0, 1, 2, and three or more
   B. Number of a's seen so far
   C. Position of the last b
   D. Length of the string mod 4
   Answer: A. The machine counts b's up to 3 and stops counting. (Key point: State meaning)

3. What happens in q3 (the final state)?
   A. It goes back to q0 on a
   B. It loops on both a and b, because once three b's are seen the string is accepted
   C. It moves to a dead state on b
   D. It loops only on b
   Answer: B. Extra symbols after the third b cannot change acceptance. (Key point: Final state behaviour)

4. For the input abab, where does the machine end?
   A. q3, so it is accepted
   B. q1, so it is rejected
   C. q2, so it is rejected
   D. q0, so it is rejected
   Answer: C. abab has only two b's, so the count reaches 2. (Key point: Trace)

## Related in Discrete Structure

- [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×
- [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×
- [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
- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×

## Related in other subjects

- [Regular expression with substring 0101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-substring-0101) — Theory of Computation, chapter 2
- [Transition curve R=2000 m, chainages, deflection table](https://www.bctengineer.com/question.md?key=semester_4%2Fsurveying_ii%3Atransition-curve-2000m-160kmh-chainage-table) — Surveying II, chapter 6
- [Regular grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2