16.3. Bit Strings with Substring '01'

Try these first

1. 1.

   What is S(2)?

   Hint

   Think about the minimal string that contains '01'.

2. 2.

   List valid bit strings of length 3 containing '01'.

   Hint

   Consider where '01' can appear in a string of length 3.

3. 3.

   Which category of strings does S(n) incorporate when starting with '1'?

   • Only strings with two 1's
   • Strings with at least one '01'
   • Only strings of length n-1

   Hint

   Think about what must hold true if the first bit is '1'.

4. 4.

   True or False: S(n) considers both cases of leading zeros and starting with '1'.

   • True
   • False

   Hint

   Reflect on how both categories are defined and their contributions to S(n).

5. 5.

   Determine the values of S(6) based on the established recurrence. Then, describe the logic.

   Hint

   Use previously computed values and step through the relation incrementally.

6. 6.

   If the concept of leading zeros is modified to allow a fixed number (like 2) before a 1 appears, reformulate S(n) to accommodate this.

   Hint

   Explore how variations in leading zero lengths adjust our recurrence.