<s>[INST] Generating function of binary string with minimum lengths for 0s and 1s a) Show that the generating function by length for binary strings where every block of 0s has length at least 2, each block of ones has length at least 3 is:
$$\frac{(1-x+x^3)(1-x+x^2)}{1-2x+x^2-x^5}$$
b) Give a recurrence relation and enough initial conditions to determine coefficients of power series.
So for a), I came up with the block decomposition $((0^*00)^*(1^*111)^*)^*$ and found the generating function, using the fact that $0\leadsto x$, $1\leadsto x$, and $a^*\leadsto\frac{1}{1-a}$ where a is some binary string:
$$\frac{(1-x)^2}{(1-x-x^2)(1-x-x^3)}$$
which, clearly, does not equal the expected result. Could someone clear up for me where I went wrong?
Also, for b), how would you find a recurrence relation, since the degree of the numerator and denominator are the same, so there would be no general $a_n$ term.
Thanks in advance for any help!
 [/INST] robjohn has given a generating function.  Here is a recurrence based approach.  
Suppose $b_n$ is the number of strings ending with $0$ and $c_n$ the number ending with $1$, and $a_n=b_n+c_n$ being what you want.  It seems obvious that 


*

*$a_n=b_n+c_n$ by definition

*$b_n=b_{n-1}+c_{n-2}$ by adding $0$ to an existing $0$ or $00$ to an existing $1$

*$c_n=b_{n-1}+c_{n-1}$ by adding $1$ to an existing $0$ or $1$
so 


*$c_n=a_{n-1}$ from (3) and (1) and so $c_{n-2}=a_{n-3}$

*$b_{n-1}=c_n-c_{n-1}=a_{n-1}-a_{n-2}$ from (3) and (4) and so $b_{n}=a_{n}-a_{n-1}$

*$a_{n}-a_{n-1}=a_{n-1}-a_{n-2}+a_{n-3}$ from (2) and (5) and (4) giving $$a_{n}=2a_{n-1}-a_{n-2}+a_{n-3}$$
That will lead to a denominator in the generating function of $1-2x+x^2-x^3$
Since $b_1=0, b_2=1, c_1=1, c_2=1$, we can find $a_0=1, a_1=1, a_2=2, a_3=4, a_4=7$ etc. But $\frac{1}{1-2x+x^2-x^3}=1+2x+3x^2+5x^3+9x^4+\cdots$ so we need to subtract $\frac{x}{1-2x+x^2-x^3} = x+2x^2+3x^3+5x^4+\cdots$ and then add $\frac{x^2}{1-2x+x^2-x^3}= x^2+2x^3+3x^4+\cdots$ to match the coefficients, with a result of $$\frac{1-x+x^2}{1-2x+x^2-x^3}$$ as robjohn found more directly
</s>