---
title: "RE: even a's followed by odd b's"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:re-even-a-odd-b"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-even-a-odd-b
site: BCT Engineering
---

# RE: even a's followed by odd b's

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2073 Chaitra
- 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-even-a-odd-b
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Write a regular expression for an even number of 'a' followed by an odd number of 'b' over the alphabet Σ = {a, b}.

## Short answer

(aa)* b (bb)*. Zero or more pairs of a's, then exactly one b followed by zero or more pairs of b's, ensuring odd total b's. Equivalent form: (aa)*(bb)*b.

## Answer

**Answer:** (aa)* b (bb)*

**Explanation.**
- (aa)* generates a string of a's of even length: ε, aa, aaaa, ... (zero is even).
- b(bb)* generates a string of b's of odd length: b, bbb, bbbbb, ...
- Concatenating them puts all the a's first and then the b's, as required.

**Examples**
- b (0 a's, 1 b) ∈ L.
- aabbb (2 a's, 3 b's) ∈ L.
- aab (2, 1) ∈ L.
- aabb (even number of b's) ∉ L, and aba (an a after a b) ∉ L.

Equivalent form: (aa)*(bb)*b.

## Check yourself

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

1. Which expression matches even a's followed by odd b's?
   A. (aa)* b (bb)*
   B. (ab)*
   C. a* (bb)*
   D. (aa)* (bb)*
   Answer: A. (aa)* is even a's and b(bb)* is odd b's. (Key point: Answer)

2. Why does b(bb)* give odd b-counts?
   A. One b plus any number of pairs
   B. It generates even b's
   C. It generates only 3 b's
   D. It allows zero b's
   Answer: A. 1 + 2m is odd. (Key point: Odd b's)

3. Which string is NOT in L?
   A. b
   B. aabbb
   C. aabb
   D. aab
   Answer: C. aabb has an even number of b's. (Key point: Examples)

## Related in Theory of Computation

- [DFA: even a and odd b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-a-odd-b) — 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
- [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
- [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
- [RE: no more than 3 a's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-at-most-3-as) — Theory of Computation, chapter 2
- [CFG for RE 0*1(0∪1)*](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-regex-0star-1) — Theory of Computation, chapter 3

## Related in other subjects

- [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×
- [Count even and odd until -1](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Acount-even-odd-until-minus1) — Computer Programming, chapter 5
- [Even and odd parts of a signal](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aeven-odd-parts) — Data Communication, chapter 2
- [Even/odd parts; time scaling and folding](https://www.bctengineer.com/question.md?key=semester_4%2Fsignals_and_systems%3Aeven-odd-parts-scaling-folding) — Signals and Systems, chapter 1