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.
Let $f(n)$ be the number of such strings of size $n$. Then the (ordinary) generating function associated with this sequence is $$F(x):=\sum\limits_{n \geq 0} f(n) x^n. $$ Based on your description, $f(n) = 1$ if $n$ is even and $f(n) = 0$ if $n$ is odd. The generating function is $$F(x) = \sum\limits_{n \geq 0}f(n) x^n = 1 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}.$$
Additionally, if we want the generating function for the number of such strings of size at most $n$, then we have $$\sum\limits_{n \geq 0 } \left(\sum\limits_{k = 0}^n f(k)\right) x^n = \frac{F(x)}{1 - x} = \frac{1}{(1 - x^2)(1 - x)}.$$
Best Answer
The generating function for the first set is
$$(x)({1\over 1-x})(x)({1\over 1-x}) = {x^2\over (1-x)^2}$$
The generating function for the second set is
$$(x)({1\over 1-x^2})(x)({1\over 1-x^2})={x^2\over (1-x^2)^2}$$
Since the generating function's coefficient represent the number of element of that length in the set, the difference of the coefficients is basically the number of elements in the difference of the two sets.
Therefore the generating function is
$${x^2\over (1-x)^2} - {x^2\over (1-x^2)^2}={2x^3+x^4\over (1-x^2)^2}$$