# Let ∑ be a finite non-empty alphabet and let 2∑* be the power set of ∑*. Which one of the following is TRUE?

0 votes
40 views
in General
closed
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

## 1 Answer

0 votes
by (41.0k points)
selected

Best answer
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

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer