A block in a bitstring s is a maximal sequence of consecutive l\'s. For example,

Question

A block in a bitstring s is a maximal sequence of consecutive l's. For example, the bitstring s = 11011101000 contains the three blocks A bitstring is called awesome,  if each of its blocks has an even length. Thus, the bitstring above is not awesome, whereas both bitstrings 00011011110 and 0000000 are awesome. For any integer n greaterthanorequalto 1, let A_n denote the number of awesome bitstrings of length n. bullet Determine A_1, A_2, A_3,  and A_4. bullet Determine the value of A_n,  i.e., express A_n in terms of numbers that we have seen in class.

Explanation / Answer

In a bitsring, if each of its block has an even length then we can say that the bitstring is awesome.

An denotes the number of awesome bitstrings of length n, So length n must be even.

Here A1 and A3 have odd length. ie; there are no awesome bitsrings.

first bitstring is 000 11 0 1111 0.

The number of awesome bitsrings of length 2 ie; A2 is 1.

The number of awesome bitsrings of length 4 ie; A4 is 1.

Second bitsting is 0000000.

The number of awesome bitsrings of length 2 and 4 are equal to 0.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.