# 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?

• Here's what I came up with : the set with the 01 strings that don't contain 00100 can be represented as 0*(0*{1, 10}*1*)*. Since each string starts with some number of zeroes(from 0 to any positive integer) and the rest of the string can be split up in substrings that starts with 0, 1, 2, ... zeroes followed by the strings "1" or "10" and any combination between these two and combinations of the combination of these two, after which we have an arbitrary number of 1's. But computing the generating function using the product lemma, I get a different answer than the correct one,which is: Commented Feb 20, 2014 at 22:33
• $\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5}$ Commented Feb 20, 2014 at 22:37
• Sorry, it seems I did not clearly understand what you wanted, and thought you want to generate such sequences, when what you need is a generating function. I will think about it. Commented Feb 21, 2014 at 1:57
• I have updated my answer. Commented Feb 21, 2014 at 19:48
• A general way of solving this is given by Odlyzco "Enumeration of Strings", in "Combinatorial Algorithms on Words" (Springer, 1985) Commented Feb 25, 2014 at 21:18

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.

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\}\}$.

• I will take a look at it and approve it later if I find it correct, thank you! Commented Feb 24, 2014 at 17:42
• You are saying that for any string that does not contain the forbidden pattern(including one that ends in the digit 0), if we add 01 to it get a "safe state" and if we add to that 0001 we get again a "safe state". But that is ___0010001 which contains the forbidden string. So a safe "state" should not end in a zero for your reasoning to be true. Also, could you write BE instead in terms of concatenation of sets of strings? Does 000 refer to (000)* or to 000*(being applied only to the last 0)? Commented Feb 24, 2014 at 18:21
• * refers to the last digit (expression if in parentheses) only. 000* means there are at least two 0's. And no, your 0010001 cannot be generated by $B$. If $B$ starts with 0* than it must follow by either 11 or 101 to arrive at the safe state, i.e. the state where we can start all over without being afraid to create the forbidden substring. I will try to add an easier explanation soon. Commented Feb 25, 2014 at 0:29
• I added another less technical explanation for the pattern. Hope it's clear now. Commented Feb 25, 2014 at 2:22