---
title: "RE: no more than 3 a's"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:re-at-most-3-as"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-at-most-3-as
site: BCT Engineering
---

# RE: no more than 3 a's

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Kartik
- Video: [Designing Regular Expressions](https://www.youtube.com/watch?v=FOhEmW_nMRs) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-at-most-3-as
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Let Σ = {a, b}. Write a regular expression for the language with all strings in Σ* with no more than 3 a's.

## Short answer

b* (a+ε) b* (a+ε) b* (a+ε) b*. This allows 0 to 3 a's with any number of b's around and between them. Alternatively, union of b*, b*ab*, b*ab*ab*, b*ab*ab*ab*.

## Answer

**Answer:** b* (a + ε) b* (a + ε) b* (a + ε) b*

**Explanation.** The strings with at most three a's have 0, 1, 2 or 3 a's, and any number of b's between and around them. Each factor (a + ε) chooses to include an a or not; b* may appear before, between and after.

```text
b*  (a|ε)  b*  (a|ε)  b*  (a|ε)  b*
```

**Examples**
- ε, b, bbb (0 a's) ∈ L.
- bab, abab, baba, abbab (≤ 3 a's) ∈ L.
- ababab (3 a's) ∈ L, but abaaba (4 a's) ∉ L.

**Alternative form:** b* + b*ab* + b*ab*ab* + b*ab*ab*ab* (a union of the cases 0, 1, 2, 3 a's).

## Check yourself

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

1. Which regular expression gives all strings over {a,b} with at most 3 a's?
   A. b*(a+ε)b*(a+ε)b*(a+ε)b*
   B. (a+ε)(a+ε)(a+ε)b*
   C. b*ab*ab*ab*
   D. (a+b)*aaa
   Answer: A. Each (a+ε) optionally contributes an a, with b* allowed before, between and after. (Key point: Regular expression)

2. What is the role of each factor (a + ε)?
   A. It forces an a to appear
   B. It allows exactly two a's
   C. It chooses to include one a or none
   D. It matches any symbol
   Answer: C. The choice between a and ε lets each slot either contribute an a or disappear. (Key point: Role of (a + ε))

3. Why is b* placed before, between and after the (a + ε) factors?
   A. To allow any number of b's anywhere around the a's
   B. To count the b's
   C. To limit the b's to three
   D. To make the number of a's even
   Answer: A. The language puts no limit on b's, so they may occur in all gaps. (Key point: Why b* between)

4. Which string is NOT in the language?
   A. ababab
   B. bbb
   C. abaaba
   D. baba
   Answer: C. abaaba has four a's, which exceeds the limit of three. (Key point: Membership)

## Related in Theory of Computation

- [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
- [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
- [Recursive iff language and complement are RE](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-iff-complement-re) — Theory of Computation, chapter 4, asked 2×
- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [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

## Related in other subjects

- [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
- [8085 ALP: transfer data with more than 3 ones](https://www.bctengineer.com/question.md?key=semester_4%2Fmicroprocessor%3Aalp-8085-ones-greater-than-3) — Microprocessor, chapter 2
- [T/F: radial more reliable than network](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Atf-radial-more-reliable-network) — Transmission and Distribution System Design, chapter 5, asked 2×
- [Why 3D graphics is more complex than 2D](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Awhy-3d-more-complex-viewing-pipeline) — Computer Graphics, chapter 4