Is repetition the origin of countability?

Question

The original question was "Do all non-regular languages have an uncountable number of strings?".

How can someone prove that..? I am squeezing my head but I can't figure it out.

And the other side of the coin: is a language always regular, if it has a countably infinite number of strings?

A bit more generally: is repetition (DFAs) the origin of countability (and/or vice versa?) and if so, why?

Thank you in advance for your help.

Answer 1

I assume by countability, you mean a set being countably infinite, like $\mathbb{N}$.

All languages over a finite alphabet are countably infinite, whether they are regular or not.

It's easy enough to show that we can encode any string in $\mathbb{N}$: just take map its letters onto $\{1,2,\ldots\}$ and interpret the string as a base-$(n+1)$ number for an alphabet with $n$ letters. (Starting at $1$ avoids the problems with multiple $0$s on the left side of a number). You can also use Gödel numbering, which is simpler but less efficient.

It's important to distinguish languages themselves from the set of languages:

• Any language over a finite alphabet is countably infinite (or finite)
• There are an uncountably infinite number of languages over any finite alphabet
• Any class of languages we describe with a finite representation (including DFAs, CFGs, Turing Machines, or even logic statements) is countably infinite. So there are more languages than we will ever have ways to talk about or describe.

So no, repetition is not the origin of countability. Even undecidable languages are countably infinite.