4
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you very much for your answer! I guess I started off from a wrong assumption and took it too far..! $\endgroup$
    – Nick
    Mar 22, 2017 at 21:42

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.