Regular expression and FSA: at least three b's

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

Transition diagram

   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.