Skip to main content

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

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.

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

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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →