Let Ai be the set of all nonempty bit strings (that is, bit strings of length at least one) of length not exceeding i. Find

a)

b)

SOLUTIONStep 1</p>

Given be the set of all non empty bit strings of length not exceeding i.

Step 2</p>

Find

We see that ,whenever , this is because for ,if the length of a string does not exceed i,then it will not exceed j.Therefore .So .

Hence