Words over a finite alphabet avoiding finitely many nonempty factors have a rational length generating function

If $B=\mathrm{\varnothing }$ and $q=\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }$, then $a_n=q^n$ and $(1-qx){\sum }_{n\ge 0}{q}^n{x}^n=1$ coefficientwise, so [L1] makes $A(x)=1\mathrm{/}(1-qx)$ rational.

Suppose now that $B$ is nonempty. After a word $w$ avoiding $B$ has been read, the automaton state is the longest suffix of $w$ belonging to $S_B$: this holds initially at $\epsilon$, and repeated application of [L2] preserves it as each accepted letter is appended.

Let $w$ avoid $B$, let $s$ be its state from step 1.2, and let $a\in \mathrm{\Sigma }$. If $wa$ contains a forbidden factor $b$, that factor ends at the appended letter, so $b=b^{\mathrm{\prime }}a$ with $b^{\mathrm{\prime }}$ a suffix of $w$; and $b^{\mathrm{\prime }}$ avoids $B$ and is a proper prefix of $b\in B$, so $b^{\mathrm{\prime }}\in S_B$. Since $s$ is the longest suffix of $w$ in $S_B$, the word $b^{\mathrm{\prime }}$ is a suffix of $s$, so $b$ is a factor of $sa$ and [L2] rejects $a$. Conversely, $s$ is a suffix of $w$, so any factor of $sa$ in $B$ is a factor of $wa$. Thus [L2] rejects exactly the extensions that cease to avoid $B$.

Steps 1.2 and 2.1 give a weight-preserving bijection between length-$n$ words avoiding $B$ and length-$n$ walks in the prefix automaton from $\epsilon$ to any state in $S_B$.

By [L3], $a_n={\sum }_{v\in S_B}(M^n{)}_{\epsilon v}$. Each series ${\sum }_{n\ge 0}(M^n{)}_{\epsilon v}{x}^n$ is rational by [L4], and their finite sum is rational by [L5]. Together with the empty-$B$ case in step 1.1, this proves the result.