Number of binary strings of length $n$ satisfying specific (ad-hoc) conditions 
Count the number of binary strings of length $n$ that satisfy the following additional conditions:
a) Two zeroes in a row are not allowed
b) Three ones in a row are not allowed
c) The string cannot begin or end with $11$ (and of course because of a) above neither can it begin or end with $00$)

 A: As a regular expression, the string matches ^1?(011?)*01?$ for $n>1$
The minimum number of zeroes is $\lfloor \frac{n+2}{3}\rfloor$. The maximum number of zeroes is $\lfloor \frac{n+1}{2}\rfloor$. For each count of zeroes, you can set up a base string consisting of alternating zeroes and ones, $0101\ldots10$, with $k$ zeroes, length $2k-1$, then insert $n-2k+1$ ones into the string in a choice of $k+1$ locations, ${k+1 \choose n-2k+1}$. Thus the answer is:
$$\sum_{k=\lfloor \frac{n+2}{3}\rfloor}^{\lfloor \frac{n+1}{2}\rfloor}{k+1 \choose n-2k+1}$$
A: mmm - I probably posted the question too quickly, anyway in last few hours, here is I think the solution in terms of recurrence relations:
Let $N(n)$ be the number of binary strings satisfying the conditions.
Let $N_1(n)$ be the number of binary strings ending in a $1$ satisfying the conditions.
Let $N_0(n)$ be the number of binary strings ending in a $0$ satisfying the conditions. Then 
$$N_0(n) = N_1(n-1) + N_0(n-3)$$
$$N_1(n) = N_0(n-1)$$
$$N(n) = N(n-2) + N(n-3)$$
with $N_0(1) = N_1(1) = N_0(2) = N_1(2) = N_0(3) = N_1(3)=1$.
