[Solved]: Proving the set of finite languages is countable without using the union of countable sets

Problem Detail: 

The list of finite languages over a finite alphabet is countable.

I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I can prove that the infinite union of countable set is countable.

However, I am sure that there is a simpler proof. Can someone help?

In my example $|\Sigma=\{0,1\}|$

Asked By : revisingcomplexity

Answered By : David Richerby

Let your finite alphabet be $\Sigma = \{a_1, \dots, a_\ell\}$ and let $\#$ be some character not in $\Sigma$. Let $L=\{w_1, \dots, w_n\}$ be a finite language over $\Sigma$. You can consider the string $\#w_1\#w_2\#\dots\#w_n$ to be a number in base $|\Sigma|+1$ by associating the symbols $a_1, \dots, a_\ell, \#$ with the base-$(|\Sigma|+1)$ digits $0, \dots, \ell-1, \ell$, respectively (starting the string with $\#$ ensures that the leading digit isn't zero). This gives a map from the set of finite languages over $\Sigma$ to a subset of the integers, so that set of languages is countable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42010