0
$\begingroup$

Let $S$ be the set of binary strings consisting of a (nonempty) block of $0$s followed by a (nonempty) block of $1$s, such that if the block of $0$s has odd length, then the block of $1$s has even length. What is the generating function for $S?$

This is what I've tried. I proved that we can generate all strings in S by the following expression $$S = \{0\}\{0\}^*\{1\}\{1\}^*\setminus\{0\}\{00\}^*\{1\}\{11\}^*.$$ But I don't know how to write generating function for the difference of two sets. Any help appricited!

$\endgroup$
1
  • 1
    $\begingroup$ The generating function for the difference is the difference of the two generating functions. $\endgroup$
    – cr001
    Feb 13, 2019 at 7:39

1 Answer 1

0
$\begingroup$

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

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