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.


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 Apr 28 '16 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 Apr 28 '16 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$ – David Richerby Apr 28 '16 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$ – jmite Apr 28 '16 at 17:07

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.