3
$\begingroup$

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\}|$

Improve this question
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ can you explain what it means it to be a number in base $|\Sigma|+1$ ? $\endgroup$ – revisingcomplexity Apr 30 '15 at 18:45
  • $\begingroup$ what about 0#0#0, would that be mapped to the same integer of 0#0? $\endgroup$ – revisingcomplexity Apr 30 '15 at 18:59
  • $\begingroup$ @revisingcomplexity Does the revised answer make it clearer how the string is a number in base $|\Sigma|+1$? I'm assuming that $w_1, \dots, w_n$ is the list of distinct words in the language, so you couldn't have $\#w_1\#w_2\#w_3=\#0\#0\#0$. $\endgroup$ – David Richerby Apr 30 '15 at 19:48
  • 1
    $\begingroup$ @anir Any finite language of finite strings uses only a finite number of symbols from the alphabet. There are only countably many finite subsets of a countable set. The set of finite languages over any countable alphabet $\Sigma$ is the union over all finite $S\subset\Sigma$ of the set of finite languages over $S$. That's a union of countably many countable sets, so it's countable. (You could probably produce a similar proof to the one in my answer, but I think it's easier to do it this way.) $\endgroup$ – David Richerby Dec 1 '19 at 18:20
  • 1
    $\begingroup$ @anir Comments here aren’t designed for follow up questions and discussion. If you want to know more about countability of sets, I suggest you look up related questions on Mathematics SE and ask a question yourself if they don’t cover what you need. (I’m suggesting Mathematics because your questions are mostly about the fundamentals of countability, and not specific to CS.) $\endgroup$ – David Richerby Dec 4 '19 at 11:45
3
$\begingroup$

Let $A$ be a finite alphabet and let $<$ be a total order on $A$. For instance, if $A = \{a,b,c\}$, let $a < b < c$. Then order the elements of $A^*$ according to the shorlex order: $u \leqslant v$ if either $|u| \leqslant |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$, where $\leqslant_{lex}$ is the usual lexicographic order. For instance, if $A = \{a, b\}$ and $a < b$, you obtain the following sequence of words: $$ 1, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, \ldots $$ Let $r(u)$ be the rank of a given word $u$ in this sequence. The map $u \to r(u)$ defines a bijection from $A^*$ to $\mathbb{N}$.

Now you want to get an injection from the set $\mathcal{P}_f(A^*)$ of all finite languages on $A^*$ into $\mathbb{N}$. Denote by $p_n$ the $n$-th prime number. Then the map $f: \mathcal{P}_f(A^*) \to \mathbb{N}$ defined, for each $L = \{u_1, ..., u_n\}$, by $$ f(L) = p_{r(u_1)}p_{r(u_2)} \dotsm p_{r(u_n)} $$ is injective.

N.B. As you can see, this construction does not use the full power of the prime numbers, and it can be modified to get a bijection from the set $\mathbb{N}\langle A\rangle$ of polynomials over $A$ to $\mathbb{N}$. A polynomial over $A$ (with coefficients in $\mathbb{N}$) can be written as a formal sum, like $$3ab + 2bb + 5bab.$$ Now if $F = k_1u_1 + \dotsm k_nu_n$, where $k_1, \ldots, k_n \in \mathbb{N}$ and $u_1, \ldots, u_n \in A^*$, one extends $f$ by setting $$ f(L) = p_{r(u_1)}^{k_1}p_{r(u_2)}^{k_2} \dotsm p_{r(u_n)}^{k_n} $$ and it is now a bijection from $\mathbb{N}\langle A\rangle$ to $\mathbb{N}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for including a lot of the detail that I skipped in my own answer, and for showing that there are other ways to code these things, too. $\endgroup$ – David Richerby May 1 '15 at 11:09
  • $\begingroup$ @david-richerby You're welcome. $\endgroup$ – J.-E. Pin May 1 '15 at 12:02
  • $\begingroup$ Does that $|\Sigma|$ contain $#$ already? $\endgroup$ – revisingcomplexity May 5 '15 at 22:58
  • $\begingroup$ There is no $#$ in $A$ in my answer. $\endgroup$ – J.-E. Pin May 5 '15 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.