Question

3. Restricted Bitstrings

An n-bit binary string is a sequence of length n over the alphabet {0,1}.

1. How many n-bit binary strings are there?
2. How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00?
3. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11?
4. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Answer 1

1. How many n-bit binary strings are there?
n places can have either 0 or 1
2^n

2. How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00?
b1 b2 = 11 or 01 or 10 only
For rest of the n-2 places it can be either 0 or 1
3 * 2^(n-2)

3. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11?
b1 b2 = 11 or 01 or 10 only
Case 1: 11 then b3 = 0 -> 2^(n-3)
Case 2: 01 then b3 = 0 -> 2^(n-3)
Case 2: 10 then b3 = 0 or 1 -> 2.2^(n-3)
2^(n-3) + 2^(n-3) + 2.2^(n-3)
= 4. 2^(n-3)
= 2^2 2^(n-3)
= 2^(n-3+2)
= 2^(n-1)

4. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?
b1 b2 = 11 or 01 or 10 only
Case 1: 11 then b3 = 0 or 1 -> 2.2^(n-3)
Case 2: 01 then b3 = 0 or 1 -> 2.2^(n-3)
Case 3: 10 then b3 = 0 -> 2^(n-3)
2^(n-3) + 2.2^(n-3) + 2.2^(n-3)
= 5 * 2^(n-3)

--------------------------------------
Hit the thumbs up if you are fine with the answer. Happy Learning!