Purchase Solution

Generating function for strings of 1's and 0's

Not what you're looking for?

Ask Custom Question

Find the generating function with respect to length for the set of {0,1}- strings having the property that each block of 1's contains an even number of 1's and each block of 0's contains an of number of 0's.

Attachments
Purchase this Solution

Solution Summary

We show how using simple algebraic means, one can obtain the generating function for strings of 1's and 0's such that all blocks of 1's are of even length and all blocks of 0's are of odd length.

Solution Preview

Let's denote the generating function of a single blocks of 1's by f(x) and the generating function of a single blocks of 0's by
g(x). We'll allow a block of 1's to be of zero length. There is only one block of length 2r of 1's, so the generating function a blocks of 1's is:

f(x) = sum from r = 0 to infinity of x^(2r) = 1/(1-x^2)

Note that the coefficient of x^n gives the number of blocks of length n. Similarly there only being one block of length 2r+1, means that the generating function of blocks of 0's is:

g(x) = sum from r = 0 to infinity of x^(2r+1) = x/(1-x^2)

Then, to find the generating function of strings, we use the fact that we have allowed blocks of 1's to be of zero length. This means that we can always take the first block of string to be block of 1's. If the string starts with a 0, then that block of 1's is taken to be of length zero. Likewise, for a finite number of blocks, the last block ...

Purchase this Solution


Free BrainMass Quizzes
Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.