generating function for binary strings that don't contain $00100$ as a substring? On an alphabet $\{0, 1\}$, what's the generating function for the set of strings that don't contain $00100$ as a substring?
I've tried writing the set of strings that don't contain $00100$ in terms of concatenations of other sets(here is where i get stuck) and then use the product lemma.
Any hint on how i might write it? 
 A: I have found an alternative and amazingly simple pattern for your sequences, that allows to calculate the generation function in a much more simple way.
Consider all blocks that end with $1$. There are two types of such blocks: $A$ which is either $1$ or $01$, and $B$ which is $000^*1$, i.e. at least two zeros followed by $1$ ($^*$ means repeat zero or more times).
Now, every sequence of $0$'s and $1's$ can be constructed as $\{A;B\}^*0^*$. That is we repeat blocks ending in $1$ and add any number of $0$'s at the end. The resulting sequence does not contain $X=00100$ iff two conditions are met: we don't have two consecutive blocks $B$, i.e. $BB$ is forbidden, and if we end the repetitive part with $B$ then the zero-tail cannot contain more than one $0$.
Overall,
$$A^*(BAA^*)^*\{B;B0;0^*\}$$
The generating functions (note, that if $Z$ has generating function $z(x)$, then $Z^*$ has generating function $\frac{1}{1-z(x)}$):
$$A=\{1;01\}:a(x)=x+x^2$$
$$B=000^*1:b(x)=\frac{x^3}{1-x}$$
And by the product lemma, for $A^*(BAA^*)^*\{B;B0;0^*\}$ we have
$$f(x)=\frac{1}{1-x-x^2}\frac{1}{1-\frac{x^4(1+x)}{(1-x)}\cdot\frac{1}{1-x-x^2}}\cdot\left(\frac{x^3}{1-x}+\frac{x^4}{1-x}+\frac{1}{1-x}\right)=$$
$$=\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5}.$$
Note, that $f(x)=1+2x+4x^2+8x^3+16x^4+31x^5+60x^6+116x^7+225x^8+437x^9+849x^{10}+\ldots$, and, indeed, we should have $n_l$ sequences of length $l$ where $n_l=2^l$ for $l\le 4$, $n_l=2^l-(l-4)2^{l-5}$ for $5\le l\le 7$, $n_l=2^l-(l-4)2^{l-5}+\sum_{k=1}^{l-7}k2^{k-1}$ for $8\le l\le 10$, etc.
A: To generate all sequences use the following pattern (an explanation follows):
$$B^*E=\{1;01;000^*1\{1;01\}\}^*\{0^*;000^*\{1;10\}\}$$
where $^*$ means repeat previous pattern, number or $\{\}$-expression zero or more times. So, for example, $000^*$ means repeat $0$ at least two times, and $\{\}^*$ means repeat the pattern inside the curly brackets zero or more times.
The generating functions are:
$$\Phi_B(x)=x+x^2+(x^4+x^5+\ldots)+(x^5+x^6+\ldots)=x+x^2+x^4+\frac{2x^5}{1-x}$$
$$\Phi_E(x)=(1+x+x^2+\ldots)+(x^3+x^4+\ldots)+(x^4+x^5+\ldots)=1+x+x^2+2x^3+\frac{3x^4}{1-x}$$
Since we can repeat $B$ any number of times, the generating function you are looking for is
$$\Phi(x)=\sum_{k=0}^{\infty}\Phi_B^k(x)\cdot\Phi_E(x)=\frac{\Phi_E(x)}{1-\Phi_B(x)}=\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5}$$

Edit: A simpler non-technical explanation of the pattern.
Suppose we want to represent any possible sequence that does not contain string $X=00100$ as a repetition of some pattern $B$. Then whatever is the subsequence generated by $B$, we must ensure that a) it does not contain $X$, b) $X$ cannot be generated by the end of this subsequence and the beginning of the next subsequence generated by $B$, and also, of course, we need c) that every sequence can be generated as the repetition of $B$.
Suppose that $B$ can start with any sequence of $0$'s and $1$'s. In this case, to satisfy b), $B$ cannot end with $0$ or $001$. If it ends with anything else, we are safe to start another $B$ with whatever we want.
What is the opposite of not ending in $0$ or $001$? The opposite of that is that $B$ either ends in $11$ or $101$ OR it is just a sequence $1$ or $01$ (these are the whole subsequences generated by $B$).
Hence, if $B$ generates one of the following: $1$, $01$ or $\ldots11$, $\ldots101$, then it satisfies b): we can start another subsequence generated by $B$ without being afraid it will collide with the previous one. This is what I call the "safe" state below.
Now, we need $B^*$ to generate all sequences that do not contain $X$. The first two $1$ and $01$ are fine and they cover all sequences starting with either $1$ or $01$: $1B^*$ and $01B^*$. What is left: subsequences starting with $00$. Let's look at the first $1$ after $00$. So, we have $000^*1$. It must be followed either by another $1$ or by $01$. And, hence, it will end with either $11$ or $101$, which will end the subsequence generated by $B$.
Overall, $B$ is one of the following: $1$, $01$, $000^*11$ or $000^*101$. This will generate all possible subsequences from one "safe" place to another, and two such sequences will never collide.
Now, to end the overall sequence, we can start generating a subsequence according to $B$, but stop at any point. This partial subsequence $E$ can be $0^*$ or $000^*1$ or $000^*10$.

Initial, more formal explanation.
Consider generating the sequence from left to right. If we want to represent the sequence as $B^*$ where $B$ is a common pattern, then $B$ needs to satisfy two criteria: all sequences generated by $B$ are correct (do not contain the forbidden string) and no ending of one $B$ plus the beginning of another one generates the forbidden string.
Let's consider 5 states: $s,s0,s00,s001,s0010$. The state $s$ is the "safe" state when every correct sequence, starting from this point, with what we have so far, does not generate the forbidden string. Obviously, we want any sequence generated by $B$ to end at the safe state, so that whatever is generated after that point does not collide with what we already have. The states $s0$ and $s00$ mean that we added one and more than one $0$ to the safe state, respectively. Finally, the states $s001$ and $s0010$ mean that we added $1$ and $10$ to the state $s00$, respectively.
Here is the diagram of all possible moves from the safe state. Once we reach the safe state again, this ends our pattern:
$$\begin{array}{}
s & +0\rightarrow & s0 & +0\rightarrow & s00 & +0\rightarrow & s00  &               &       &               &   \\
  &               &    &               &     & +1\rightarrow & s001 & +0\rightarrow & s0010 & +1\rightarrow & s \\
  &               &    &               &     &               &      & +1\rightarrow & s     &               &   \\
  &               &    & +1\rightarrow & s   &               &      &               &       &               &   \\
  & +1\rightarrow & s  &               &     &               &      &               &       &               &
\end{array}$$
Hence, $B=\{1;01;000^*1\{1;01\}\}$. Now, since the sequence may end at the state which is not safe, we need to add pattern $E$ which is any sequence according to the diagram above that does not end at the safe state, i.e. $E=\{0^*;000^*\{1;10\}\}$.
