2 I missed a "finite"
source | link

A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.

A language is a set of finite strings over some alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.

A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.

1
source | link

A language is a set of finite strings over some alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.