Kenneth Rosen Edition 7 Exercise 6.1 Question 12 (Page No. 396)

Question

How many bit strings are there of length six or less, not counting the empty string?

Comments

Can I do this with Complement Rule?
Total-(bit string of length 7 or more)?

But, what will be total in this case?

And, how can I perform this part(bit string of 7 or more)?

---

Yeah, I can do this question using complement rule & IEP but the more intuitive way is done by Saitheja 

Refer the attachment to see, how can we do this question using complement rule & IEP : 

Answer 1

1. 2^6 includes all binary strings of length less than or equal to 6. ----→ WRONG. It only includes all binary strings of length equal to 6.
2. Binary strings of length 1 are {0,1}. Binary strings of length 2 are {00,01,10,11}. Binary strings of length 3 are {000,001,010,011,100,101,110,111}.
3. Don’t confuse values with strings. ‘000’ and ‘0’ these two are different strings, ‘000’ is length 3 string and ‘0’ is length 1 string. But when we see it as numbers then they both have same values. So, both string ‘000010’ and ‘000100’ are length 6 strings.

Answer 2

To find the number of bit strings of length six or less, not counting the empty string, we can use the following approach:

• For a string of length 1, there are 2 possibilities (0 or 1).
• For a string of length 2, there are 2 possibilities for each of the 2 positions, giving a total of 2 x 2 = 4 possibilities.
• For a string of length 3, there are 2 possibilities for each of the 3 positions, giving a total of 2 x 2 x 2 = 8 possibilities.
• For a string of length 4, there are 2 possibilities for each of the 4 positions, giving a total of 2 x 2 x 2 x 2 = 16 possibilities.
• For a string of length 5, there are 2 possibilities for each of the 5 positions, giving a total of 2 x 2 x 2 x 2 x 2 = 32 possibilities.
• For a string of length 6, there are 2 possibilities for each of the 6 positions, giving a total of 2 x 2 x 2 x 2 x 2 x 2 = 64 possibilities.

Therefore, the total number of bit strings of length six or less, not counting the empty string, is:

2 + 4 + 8 + 16 + 32 + 64 = 126

So there are 126 bit strings of length six or less, not counting the empty string.

Answer 3

Given Strings of length of length six or less

Every bit has two values i.e., 0 or 1

six length = 2 x 2 x 2 x 2 x 2 x 2 = 64

Five length  = 2 x 2 x 2 x 2 x 2 = 32

Four length = 2 x 2 x 2 x 2 = 16 

Three length = 2 x 2 x 2 = 8

Two length = 2 x 2 = 4

one length = 2 

∴ Bit strings of length six or less is 64 + 32 + 16 + 8 + 4 + 2 =126