# Can a regular language have uncountably many strings?

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.)
• 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. – MSalters Apr 28 '16 at 14:01
• @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. – David Richerby Apr 28 '16 at 14:54