A set is countable means there exist a enumeration procedure to generate each of its elements and for a given element of set, it take finite step to generate it using the enumeration procedure.

Let $\Sigma = \{a,b \}$ and there exist a enumeration procedure to generate all the string of the language $\Sigma^*$.

$\Sigma^{*}=\{ \epsilon , a , b , aa, ab, ba, bb , aaa , \ldots \}$

Here, enumeration procedure is simply the generating string of the language by length for the fixed length string are in alphabetical order.

This way $\Sigma^{*}$ is countably infinite & $2^{\Sigma ^{*}}$ will be uncountable set

Because the power set of any countably infinite set is uncountable.

Theorem- S is a countably infinite set, 2 S (the power set) is uncountably infinite.

Proof: We show 2 S is uncountably infinite by showing that 2 N is uncountably infinite. (Given the natural bijection that exists between 2 N and 2 S –because of the bijection that exists from N to S– it is sufficient to show that 2 N is uncountably infinite.) Assume that the set 2 N is countably infinite. The subsets of N can be listed A0, A1, A2, . . . so that every subset is Ai for some i. We define another set A = {i|i ≥ 0 and i 6∈ Ai} which contains those integers i which are not members of their namesake set Ai . But A is a subset of N, and so A = Aj for some j. But this means 1. If j ∈ A, then j 6∈ A. 2. If j 6∈ A, then j ∈ A. We have a contradiction, since j must either be in the set A or not in the set. Therefore 2 N is not countably infinite. ⋄ The Theorem that the power set of a countably infinite set is an uncountable set indicates that the set of all languages over any alphabet Σ, |Σ| 6= 0 is uncountable. (2 Σ∗ is an uncountable set.)