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
