Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no, but I can't really back it up.


2 Answers 2


No, there are only countably many finite strings over any finite alphabet. Given an alphabet $\Sigma = \{s_0, \dots, s_d\}$, you can associate the string $w$ with the number $1w$ written in base-$d$, giving an injection from the natural numbers to $\Sigma^*$. (The reason we use the number $1w$ rather than $w$ is to avoid problems with, e.g., $2$, $02$, $002$, etc. all mapping to the same number.)

  • $\begingroup$ Plus, countability survives taking subsets. $\endgroup$
    – Raphael
    Commented Apr 28, 2016 at 11:31
  • $\begingroup$ I'm not sure if this is an exact answer. There are countably many finite strings, but infinite strings are not countable per Cantor's diagonalization argument. What makes them non-regular? In other words, a real number 0<= x <1 can be thought of as a word from the lanugage 0.[0-9]*, and that's uncountable. $\endgroup$
    – MSalters
    Commented Apr 28, 2016 at 14:01
  • 1
    $\begingroup$ @MSalters Regular languages are, by definition, languages of finite strings. If you want to talk about $\omega$-regular languages of infinite strings, that's a whole 'nother question. Also a real number isn't uncountable: it's one thing. $\endgroup$ Commented Apr 28, 2016 at 14:54

Yes,a regular language can have uncountable number of strings as a regular language can have unlimited strings by Kleene closure or sigma closure.

  • $\begingroup$ This is wrong link. Uncountable is not the same as infinite. $\endgroup$ Commented Apr 28, 2016 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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