Generating function for strings of 1's and 0's
Not what you're looking for?
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.
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.