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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.)
answered Apr 28, 2016 at 4:12
-
$\begingroup$ Plus, countability survives taking subsets. $\endgroup$– Raphael ♦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$– MSaltersApr 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$ Apr 28, 2016 at 14:54
$\begingroup$
$\endgroup$
1
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$– jmiteApr 28, 2016 at 17:07