Question

2. For L = {a, bb}, how many strings of length 10 are there in L ∗

Answer 1

Given L = {a, bb}.

Solution :

Strings of Length 1: 'a' ==>One string

Strings of Length 2: 'aa', 'bb' ==> Two strings

Strings of Length 3: aaa, 'bba', 'abb' ==>Three strings

Observe the above pattern,

We are getting string of length n,

• By appending string "a" to a string which is of length n−1 and
• By appending "bb" to a string which is of length n−2.

Therefore, Length(n) = Length(n-1) + Length (n-2)

n	Number of strings
1	1
2	2
3	2 + 1 =3
4	3 + 2= 5
5	5 + 3 = 8
6	8 + 5 =13
7	13 + 8 = 21
8	21 + 13 = 34
9	34 + 21 = 55
10	55 + 34 = 89

Note that 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 is fibonacci series. Tenth fibonacci number is 89.

Therefore, Total number of strings of length 10 are 89.