Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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:
So no, repetition is not the origin of countability. Even undecidable languages are countably infinite.
