DFA Design: Strings over $\{a,b\}$ with at least three occurrences of the substring $bbb$ (overlap allowed)

We want a deterministic finite automaton (DFA) over the alphabet $\{a,b\}$ that accepts exactly the strings containing at least three occurrences of the substring $bbb$, where occurrences may overlap. For example, $bbbbb$ contains occurrences at positions $1\!-\!3$, $2\!-\!4$, and $3\!-\!5$, so it must be accepted.

A robust way to build such a DFA is to track:

1. How much of the current suffix could still be part of a future $bbb$ (i.e., the last $0,1,2$ symbols of a potential $bbb$ ending),
2. How many $bbb$ occurrences have already been completed,
3. And to increment the count whenever the transition produces a completed $bbb$.

We will use the standard “prefix-suffix” memory for the pattern $bbb$, i.e., track the longest suffix of the processed input that is also a prefix of $bbb$.

Key concepts:

• Deterministic finite automaton (DFA)
• Substring occurrence
• Overlapping occurrences
• Prefix of a pattern

Mermaid view of the idea:

Formal target language

Let $\Sigma=\{a,b\}$. Define the set of strings

$$L=\{\,w\in\Sigma^* \mid w \text{ contains at least 3 (possibly overlapping) occurrences of } bbb\,\}.$$

We can formalize an “occurrence” as: $bbb$ occurs starting at position $i$ if the length-3 factor $w[i]w[i+1]w[i+2]=bbb$.

To handle overlap, we must ensure that after reading a symbol that completes one occurrence, the automaton continues tracking suffixes that may begin another occurrence immediately.

State design strategy (suffix memory + count)

The pattern is $bbb$. Its prefixes are:

• length $0$: $\epsilon$
• length $1$: $b$
• length $2$: $bb$
• length $3$: $bbb$ (a completion)

Let the DFA state be a pair:

• count
• suffix

We only need suffix lengths $0,1,2$ explicitly; suffix length $3$ is handled by “increment count then fall back to the appropriate suffix” (because overlaps are allowed).

We cap the count at $3$: once we’ve seen $3$ occurrences, we stay in an accepting “done” region.

Suffix transitions for the pattern $bbb$ when reading symbols

Let suffix memory $m\in\{0,1,2\}$ mean:

• $m=0$: suffix is “nothing useful” (no trailing $b$ prefix)
• $m=1$: suffix is $b$
• $m=2$: suffix is $bb$

Now compute updates on reading next symbol:

• Reading $a$ always breaks any run of $b$:

  • from any $m$: suffix becomes $0$ (because suffix cannot end in $b$).

• Reading $b$ extends a run:

  • from $m=0$ (“no trailing b-prefix”) reading $b$ gives suffix $1$ (“ends with $b$”)
  • from $m=1$ reading $b$ gives suffix $2$ (“ends with $bb$”)
  • from $m=2$ reading $b$ completes one $bbb$ occurrence:
    • count increments
    • after consuming that $bbb$, the new suffix that can start another $bbb$ due to overlap is the suffix $bb$ (because the last two symbols are $bb$)

That last step is the overlap mechanism: in a run of $b$’s, consecutive $bbb$ windows share characters.

[CalloutBlock] type="tip" title="Pro Tip" content="When overlaps are allowed, don’t reset to 0 after finding a match. Instead, compute the longest suffix that is also a prefix of the pattern (here, after matching $bbb$ the remaining suffix is $bb$)."

Complete DFA specification

State set

Let

$$Q=\{(c,m)\mid c\in\{0,1,2,3\},\ m\in\{0,1,2\}\}.$$

Start state:

$$q_0=(0,0).$$

Accepting states:

$$F=\{(3,0),(3,1),(3,2)\}.$$

Transition function $\delta$

For any $c\in\{0,1,2,3\}$:

1. On input $a$:

$$\delta((c,m),a)=(c,0)\quad \text{for } m\in\{0,1,2\}.$$

2. On input $b$:

• If $m=0$:

$$\delta((c,0),b)=(c,1)$$

• If $m=1$:

$$\delta((c,1),b)=(c,2)$$

• If $m=2$ (completion):

$$\delta((c,2),b)=(\min(c+1,3),2)$$

This DFA is deterministic because for each state and each symbol $a,b$, exactly one next state is defined.

[CalloutBlock] type="warning" title="Warning: counting overlaps correctly" content="The only time the count increases is when $m=2$ and the next symbol is $b$. This correctly counts overlapping $bbb$ windows (e.g., $bbbbb$ adds three matches)."

Transition table (compact)

Let $c'$ denote $\min(c+1,3)$.

where $c\in\{0,1,2,3\}$ and $c'=\min(c+1,3)$.

Example runs (to validate overlap)

Example: $bbbbb$

Track $(c,m)$:

• Start $(0,0)$
• read $b$: $(0,0)\to(0,1)$
• read $b$: $(0,1)\to(0,2)$
• read $b$: $(0,2)\to(1,2)$ (first $bbb$ completed)
• read $b$: $(1,2)\to(2,2)$ (second completed, overlapping)
• read $b$: $(2,2)\to(3,2)$ (third completed)

Since $c=3$, the string is accepted.

Example: $bbbabb b$ idea

Any time an $a$ appears, $m$ resets to 0, which prevents $bbb$ from completing across the $a$.

State diagram (pattern counter “layered by count”)

Below is a structural view: from each count layer, reading $b$ advances suffix memory; hitting $m=2$ and reading $b$ moves to the next count layer while staying at $m=2$.