Question

Let ∑ be a finite non-empty alphabet and let 2^∑* be the power set of ∑*. Which one of the following is TRUE?
1. Both 2^∑* and ∑* are countable 
2. 2^∑* is countable and ∑* is uncountable 
3. 2^∑* is uncountable and ∑* is countable 
4. Both ) 2^∑* and ∑* are uncountable 

Answer 1

Correct Answer - Option 3 : 2^∑* is uncountable and ∑* is countable 

Set of all strings over any finite alphabet are countable. Therefore, ∑* is countable.

Moreover, a set is countable if there exists an enumeration procedure to generate each of its elements and for a given element of set, it takes finite step to generate it using the enumeration procedure.

Note that, ∑* is countable but it is countably infinite.

According to Diagonalization Method, If ∑* is countably infinite then 2^∑* is uncountable