Let S be the set of binary strings consisting of a (nonempty) block of Os followed...

 

Transcribed Image Text:

Let S be the set of binary strings consisting of a (nonempty) block of Os followed by a (nonempty) block of 1s, such that if the block of Os has odd length, then the block of 1s has even length. Let an be the number of strings of length n in S. (a) Find ao, a1, a2, a3. (b) Prove that S = {0}{0}*{1}{1}* \ {0}{00}*{1}{11}*. (c) Show that the generating function for S is x (2+x) s(x) = (1-x)2 (d) Write down a recurrence equation for an. Determine a closed formula for an for all n, and find a1001. Let S be the set of binary strings consisting of a (nonempty) block of Os followed by a (nonempty) block of 1s, such that if the block of Os has odd length, then the block of 1s has even length. Let an be the number of strings of length n in S. (a) Find ao, a1, a2, a3. (b) Prove that S = {0}{0}*{1}{1}* \ {0}{00}*{1}{11}*. (c) Show that the generating function for S is x (2+x) s(x) = (1-x)2 (d) Write down a recurrence equation for an. Determine a closed formula for an for all n, and find a1001.

Answer rating: 100% (QA)

a a0 The set S cannot contain a string of length 0 because it must have a nonempty block of 0s follo... View the full answer