\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

Section 8.1 Forbidden Words

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 \[\eps+L(0+1) = L+M.\tag{8.1.1}\label{eq-eL01}\] 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\}\]

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).\]

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

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

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.

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 \begin{align} \eps+L(0+1) &= L +M_1 +M_2\notag\\ L\al_1 &= M_1(\al_1\backslash\al_1) +M_2(\al_1\backslash\al_2)\notag\\ L\al_2 &= M_1(\al_2\backslash\al_1) +M_2(\al_2\backslash\al_2).\notag \end{align} Write a program that, given \(\al_1\) and \(\al_2\), computes the generating series for \(L\), \(M_1\) and \(M_2\).