Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It would be helpful to know the cardinality of $\Sigma$. $\endgroup$Kai– Kai2023-09-13 00:51:24 +00:00Commented Sep 13, 2023 at 0:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$\lambda$, $a$, $b$, $aa$, $ab$, $ba$, $bb$, $aaa$, $aab$, $aba$, $abb$, $baa$, $bab$, $bba$, $bbb$, $aaaa$, $\dots$,
$\begingroup$
$\endgroup$
Let us assume your set is $S=\cup_{n\geq1}\Sigma^n$. Clearly, this set is infinitely large. All that is left to figure out is if $S$ is countable.
Any set with a bijection to the set of Natural Numbers, i.e., $\{0,1,2,\ldots\}$, is countable.
Use the above fact to determine why $S$ is an infinitely large countable set.
