Math 249 Midterm November 9, 4:30 – 6:20 pm 1. Determine the generating series for L, the language consisting of the binary strings that do not contain 010 or 101. 2. Use a block decomposition of the set of binary strings to determine the generating series for the set of strings where each block of 0’s has length at least two, and each block of 1’s has length at least three. 3. Let the generating series L(x) be given by L(x) = 1 + x4 . 1 − 2x + x4 − x5 Determine a linear recurrence satisfied by the coefficients of L and use this to calculate the coefficient of x6 . 4. Find the generating series for the number of compositions of an integer into an odd number of parts, each of which is at least three. 5. Use the identity Y 1 − atxr r≥0 1 − txr = X n≥0 n t n Y 1 − axk−1 k=1 1 − xk to prove that n−1 Y i=0 X n + j − 1 1 = tj . i j 1−q t j≥0 1 .
© Copyright 2024 ExpyDoc
![Mango - Welcome [Savannah]](http://s1.expydoc.com/store/data/006522585_1-bffdc62bf8a1ccc7c5af6b0bd95d3ee2-250x500.png)
