Please write your solutions as clearly and concisely as possible.

1. (30 pts) For each of the following sets, say whether it is countable or uncountable. Justify your answer formally.
   1. (5 pts) The set of all finite strings on a finite alphabet Sigma = {a₁, a₂, ... , a_k} with k>=2
   2. (10 pts) The set of all infinite strings on a finite alphabet Sigma = {a₁, a₂, ... , a_k} with k>=2
   3. (15 pts) The set of all finite strings on a infinite alphabet Sigma = {a₁, a₂, ... , a_k, ... }

2. (20 pts) Assume that L, L₁ and L₂ are recursively enumerable sets.
   1. Is L₁L₂ recursively enumerable?
   2. Is L^* recursively enumerable?
   Justify your answer.

3. (20 pts) Assume that L, L₁ and L₂ are recursive sets.
   1. Is L₁L₂ recursive?
   2. Is L^* recursive?
   Justify your answer.

4. (30 pts) For each of the following languages, say whether it is recursive / recursively enumerable / not recursively enumerale. Justify your answer.
   1. L₁ = { x in {0,1}^* | there exists a TM M s.t. x = e(M) and M does not accept any string in {0,1}^* }
   2. L₂ = { x in {0,1}^* | there exists a TM M s.t. x = e(M) and M accepts at least one string in {0,1}^* }
   3. L₃ = { x in {0,1}^* | there exists a TM M s.t. x = e(M) and M accepts all strings in {0,1}^* }
   In the above definitions, x = e(M) means that x is the string representing the encoding of the TM M.