How to prove Kleene star to be uncounably infinite?

Question

I have the language $L = \{a, b\}$. How can I prove that the Kleene star (set of all words over the language) of this language is uncountably infinite or countably infinite?

Answer 1

Let $L = \{a, b\}$. Denote by $L_k$ the set of all words of length $k$ over $L$.

Proposition 1: $|L_k| = 2^k, \forall k \in \mathbb{N}.$

Proof. Induction by $k$. For $k = 0$ (or $k = 1$) it is obvious. Fix some $n \in \mathbb{N}$ and assume that the proposition holds for all $k \leq n$. Any word $w \in L_{n + 1}$ can be uniquely written as the concatenation of some word $v \in L_n$ and a letter $c \in L$, i.e. $w = vc$. And conversely each word $v \in L_n$ "generates" two different words $va$ and $vb$ from $L_{n+1}$. Hence $|L_{n+1}| = 2|L_n| = 2^{n+1}.$

Proposition 2: $L^* = \bigcup_{i \in \mathbb{N}}L_i.$

Proof. Definition of $L^*$.

From these propositions it follows that $L^*$ is a countable union of finite sets which is a countable set itself (roughly, you can enumerate each $L_k$ consequently and each $L_k$ will be enumerated after finite number of steps).

Answer 2

Choose $a$ to be the digit $1$ and $b$ to be the digit $0$.

Consider a string from the language $S$, and prepend a $1$ to it. For example, $\text{babba}$ becomes $1\underbrace{01001}_\text{babba}$. That is a unique integer in binary.

It should be obvious (if you are familiar with binary) how to convert between strings in your language and $\mathbb Z^{+}$. So the language is countable.