Generating function for special string 11100 
Let $S$ be the set of $\{0,1\}$-strings that do not contain $11100$ as a string. Find the generating function of S where the weight of a string is its length. 

I tried this way :
Consider all blocks that end with $0$. There are two types of such blocks: $A$ which is either $0$ or $10$, and $B$ which is $1111*0$. (∗ means repeat one or more times).
Now, every sequence of $0$'s and $1$′s can be constructed as $\{A;B\}∗1\,∗$. The resulting sequence does not contain $=11100$ iff two conditions are met: we don't have two consecutive blocks $BA$, i. e. $BA$ is forbidden.
But I am not sure this concept. Please help me.
Thanks your idea.
 A: This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $\mathcal{V}=\{0,1\}$ and the set $B=\{11100\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being  the number of valid  words of length $n$.

According to the paper (p.7) the generating function $f(s)$  is
\begin{align*}
f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[11100])
\end{align*}

We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[11100])&=-s^5\tag{2}\\
\end{align*}
It    follows  from  (1)  and (2)
\begin{align*}
\color{blue}{f(s)}&\color{blue}{=\frac{1}{1-2s+s^5}}\\
&=1 + 2 s + 4 s^2 + 8 s^3 + 16 s^4\\
&\qquad+ 31 s^5 + \color{blue}{60} s^6 + 116 s^7 + 224 s^8 \cdots
\end{align*}

The last line was calculated with the help of Wolfram Alpha.  The coefficient   of $s^6$ for example shows there are $\color{blue}{60}$ valid words of  length $6$ from the alphabet $\{0,1\}$ which do not contain the word $11100$. The invalid $2^6-60=4$ words are
\begin{align*}
\color{blue}{0}11100,\quad \color{blue}{1}11100,\quad 11100\color{blue}{0},\quad 11100\color{blue}{1}
\end{align*}
A: We use the symbolic method to derive a generating function $f(s)$.

Let $\mathcal{F}$ denote   the set of all valid words, i.e. the set of all binary words which do not contain the word $11100$. We  have
  \begin{align*}
\color{blue}{\varepsilon+\mathcal{F}\{0,1\}=\mathcal{F}+\mathcal{F}\{11100\}}\tag{1}
\end{align*}

The left-hand side  of  (1)  consists  of


*

*$\mathcal{F}\{0,1\}$:  The set of all valid words which have additionally appended either a $0$ or a $1$ at the end. These words have all length at least $1$.

*$\varepsilon$:   We add the empty word which is not part of $\mathcal{F}\{0,1\}$.
The right-hand side of (1):


*

*Note that $\mathcal{F}\{0,1\}$ contains the set of all valid words $\mathcal{F}$, but not the empty word $\varepsilon$.

*Invalid words contained in $\mathcal{F}\{0,1\}$ occur at the end only due to the appended $\{0,1\}$ at the end, resulting in $\mathcal{F}\{11100\}$.
Note that \begin{align}\varepsilon\cap \mathcal{F}\{0,1\}=\emptyset\qquad\text{ and }\qquad\mathcal{F}\cap \mathcal{F}\{11100\}=\emptyset.\end{align} So,  we  have at both sides  of  (1) a partition which avoids multiple counting of words.

From (1) we obtain the generating function $f(s)$ in the form
\begin{align*}
1+f(s)\cdot (s+s)&=f(s)+f(s)s^5\\
\end{align*}
  which results in
  \begin{align*}
\color{blue}{f(s)}&\color{blue}{=\frac{1}{1-2s+s^5}}\\
\end{align*}

