1
$\begingroup$

Suppose I want to find the generating series for $L$, where $L$ is the set of binary strings that do not contain $11010$ as a substring.

I understand that the solution works, but I don't really have good understanding for the motivation behind this approach. We let $M$ denote the set of binary strings which contain $11010$ only once at the end of the string.

$$ \{ \epsilon \} \cup L \{ 0, 1\} = L \cup M $$ $$ L \{ 11010 \} = M $$

We can then use these relationships to derive the generating series, $\Phi_L(x)$.

Is this approach merely trying to find a system of equations that can be used to solve for $\Phi_L(x)$ or is there deeper insight underlying the setup of this system?

$\endgroup$
1
$\begingroup$

This is basically an instance of the symbolic method, which has quite a few uses. The idea is that you can construct a combinatorial class ($L$, for instance) out of building blocks (possibly containing itself) like union, product (which is what concatenation is in your case), sequences, sets, multisets and cycles.

The idea is that the statement $$\{\epsilon\} \cup L\{0,1\} = L \cup L\{11010\}$$ uniquely defines the combinatorial class. One application---as you mention---is that it lets you read off the generating function immediately: $$1 + f(x)(2x) = f(x) + f(x)x^5 \implies f(x) = \frac{1}{1 - 2x + x^5}.$$

It's also possible to use the above to get a recurrence relation: $$L_{n+1} = 2L_n - L_{n-4},\qquad L_0 = 1.$$

On the slightly more obscure side, you can often use this sort of construction to perform something called Boltzman Sampling (see these slides for a brief introduction), which allows you to uniformly sampling elements of $L$ of a given size relatively quickly.

To summarize, and zoom out a bit, a statement like $\{\epsilon\} \cup L\{0,1\} = L \cup L\{11010\}$ is a symbolic way of summarizing your combinatorial interpretation, and thus carries all information about the sequence.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.