Advanced Topics · Lesson 9

Factor Avoidance

Avoidance

Fix a nonempty pattern $P \in Σ_{k}^{m}$ . A word avoids $P$ if it has no occurrence of $P$ as a factor. Let $a_{P} (n)$ be the number of length- $n$ words over $Σ$ _k that avoid $P$ .

Testing one word is easy — run KMP. Counting all avoiding words is different: we should not list the $k^{n}$ words individually.

Deterministic finite automata

A DFA is a 5-tuple $M = (Q, Σ, δ, q_{0}, F)$ :

a finite nonempty set of states $Q$ ,
a finite input alphabet $Σ$ ,
a transition function $δ : Q \times Σ \to Q$ ,
a start state $q_{0}$ ,
a set of accept (final) states $F$ .

A word is accepted if, starting in $q_{0}$ , the path labeled by its symbols ends in an accept state. A sink state $⊥$ rejects every path that touches it.

The avoidance automaton

To recognize words that avoid $P$ , let the states remember how close the word read so far is to ending in an occurrence of $P$ . As long as $P$ has not occurred, the only relevant information is the longest suffix of the word read that is a prefix of $P$ . So the useful states are

ε, P [1], P [1 .. 2], \dots, P [1 .. m - 1]

with $ε$ as the start state.

On reading a symbol $a$ , append it and find the longest suffix of the result that is a prefix of $P$ :

if reading $a$ completes $P$ , move to the rejecting sink $⊥$ ;
otherwise move to the state for that longest proper prefix.

Every non-sink state is accepting, because reaching it means no occurrence of $P$ has appeared yet. And this is exactly the information KMP uses: when the longest candidate cannot be extended, the failure function tells us which shorter prefixes remain possible.

Avoiding 010 over 2-letter alphabet { 0, 1 }. The states record the longest suffix of the word read so far that is a prefix of 010.

Start in state 0 (ε) — no letters read yet.

A longer example

The pattern 01001 shows why a mismatch need not send us all the way back to $ε$ . From the state recording 010, reading 1 gives the word 0101, whose longest suffix that is a prefix of 01001 is 01 — not $ε$ .

Avoiding 01001 over 2-letter alphabet { 0, 1 }. The states record the longest suffix of the word read so far that is a prefix of 01001.

Start in state 0 (ε) — no letters read yet.

As a check, 010001 follows the states $0 \to 1 \to 2 \to 3 \to 4 \to 1 \to 2$ and is accepted, while 01001 reaches $⊥$ on its final letter.

Counting paths instead of listing words

For each accepting state $s$ , let $a_{s} (n)$ count the avoiding words of length $n$ whose final state is $s$ . Then

a_{0} (0) = 1, a_{s} (0) = 0 (s > 0)

and each word has a unique last symbol and a unique path, so

a_{t} (n + 1) = \sum_{s}^{m - 1} \sum_{a \in Σ_{k}, δ (s, a) = t} a_{s} (n)

Different letters leading from the same state to the same next state count separately — they produce different words.

For 010, this gives the recurrence

a_{0} (n + 1) = a_{0} (n) + a_{2} (n), a_{1} (n + 1) = a_{0} (n) + a_{1} (n), a_{2} (n + 1) = a_{1} (n)

so $a_{010} (n)$ goes 1, 2, 4, 7, 12, 21, 37, … At length three only 010 itself is excluded; for longer words the state counts retain exactly the suffix information needed.

A recurrence for the total alone

The state recurrences can be combined into a single recurrence involving only $a_{P} (n)$ . The technique is to push $n$ forward through the recurrences and collect coefficients on $a_{s} (n)$ , then check which combination cancels.

For 010, expanding the sum $a_{010} (n) = a_{0} (n) + a_{1} (n) + a_{2} (n)$ through the recurrences three times gives

a_{010} (n + 3) - a_{010} (n + 2) - a_{010} (n + 1) - a_{010} (n) = 0

so the totals alone obey the tribonacci recurrence $a_{010} (n) = a_{010} (n - 1) + a_{010} (n - 2) + a_{010} (n - 3)$ — check: 7 = 4 + 2 + 1, 12 = 7 + 4 + 1, 21 = 12 + 7 + 2, 37 = 21 + 12 + 4.

For the pattern 001 the cancellation leaves a nonzero remainder. Its state recurrences are

a_{0} (n + 1) = a_{0} (n) + a_{1} (n) a_{1} (n + 1) = a_{0} (n) a_{2} (n + 1) = a_{1} (n) + a_{2} (n)

Here $a_{0} (n) - a_{2} (n)$ is invariant (its own recurrence is the difference of the first and third lines above), and $a_{0} (2) - a_{2} (2) = 2 - 1 = 1$ , so

a_{001} (n + 2) - a_{001} (n + 1) - a_{001} (n) = a_{0} (n) - a_{2} (n) = 1

so $a_{001} (n) = a_{001} (n - 1) + a_{001} (n - 2) + 1$ , giving 1, 2, 4, 7, 12, 20, 33, … — each total is the sum of the previous two plus one.

Practice

Trace a transition

In the avoidance DFA for 10, which state does state 0 (recording ε) reach on reading 1? Use the pattern length for the sink ⊥.

In the avoidance DFA for 0101, which state does state 3 (recording "010") reach on reading 0? Use the pattern length for the sink ⊥.

Count the avoiding words

How many length-3 words over a 2-letter alphabet avoid 001?

How many length-8 words over a 3-letter alphabet avoid 010100?

Practice this topic →Every quiz from this lesson, at four difficulties.