Let $\al$ denote a binary string, and let $L$ denote the set of binary of binary strings that do not contain $\al$ as a substring. How many strings are there in $L$ with length $n$?

Let $M$ denote the binary
strings that contain exactly one copy of $\al$, as a suffix.
If $\eps$ denotes the empty string, then
\begin{equation}
\label{eq:eL01}
\eps+L(0+1) = L+M.
\end{equation}
Also $L\al$ clearly contains $M$ as a subset, but for example if $\al=111$,
then
\[
L\al =M+M1+M11.
\]
We develop a precise description of $L\al$. Let $\al\backslash\be$ denote the
set of suffixes $\be_1$ such that
$\be_0\be_1=\be$ and $\be_0$ is a suffix of $\al$. For example if
\[
\al =100110,\quad \be=1011,
\]
then
\[
\al\backslash\be = \{11\},\quad \al\backslash\al = \{\eps,0110\}
\]
**Lemma**
\[
L\al = M\al\backslash\al.
\]

Note that $\al\backslash\al$ is a finite language, i.e., a finite set of strings.

If $N$ is a set of binary strings, let $N(t)$ denote its generating series.
This is what we get when we substitute $t$ for $0$ and $1$, a string of length
$\ell$ maps to $t^\ell$ and the language maps to its generating series.
Now \eqref{eq:eL01} yields
\[
1+2t L(t) = L(t)+M(t)
\]
and, if $D=\al\backslash\al$ and $|\al|$ denotes the length of $\al$,
the lemma yields that
\[
L(t)t^{|\al|} = M(t) D(t).
\]
**Lemma**
\[
L(t) =\left(1-2t+\frac{t^{|\al|}}{D(t)}\right)^{\!-1}.
\]

Let's use this to compute some numbers. We first set up the ring of formal power series over the rationals.

Rt.<t> = QQ[[]]; Rt

Power Series Ring in t over Rational Field

If $\al=111$, then $D(t)=1+t+t^2$ and $L(t)$ is

L = ((1-2*t+ t^3/(1+t+t^2))^(-1)).O(9); L

1 + 2*t + 4*t^2 + 7*t^3 + 13*t^4 + 24*t^5 + 44*t^6 + 81*t^7 + 149*t^8 + O(t^9)

As an exercise, write a program which takes a binary string $\al$ and computes the generating series for $\al\backslash\al$. (The string arrives as a Python string, there is no reason why your procedure should not work for strings over an arbitrary alphabet.)

The square root of the series $L(2t)$ has non-negative integer coefficients.

L.subs(t=2*t).sqrt()

1 + 2*t + 6*t^2 + 16*t^3 + 54*t^4 + 180*t^5 + 596*t^6 + 2048*t^7 + 7062*t^8 + O(t^9)

Does this hold for other forbidden substrings?

For a second variant, suppose $\cF=\{\seq\al1d\}$ is a set of binary strings. Let $L$ be the set of strings that contain no element of $\cF$ and let $M_i$ denote the set of strings that contain one copy of $\al_i$, as a suffix, bit do not contain any other copies of strings in $\cF$. If $|\cF|=2$, we have equations \begin{align*} \eps+L(0+1) &= L +M_1 +M_2\\ L\al_1 &= M_1(\al_1\backslash\al_1) +M_2(\al_1\backslash\al_2)\\ L\al_2 &= M_1(\al_2\backslash\al_1) +M_2(\al_2\backslash\al_2). \end{align*} Write a program that, given $\al_1$ and $\al_2$, computes the generating series for $L$, $M_1$ and $M_2$.