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

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

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

xxxxxxxxxx

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

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

xxxxxxxxxx

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

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.

xxxxxxxxxx

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

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, but do not contain any other copies of strings in $\cF$. If $|\cF|=2$, we have equations