2 I missed a "finite" edited Dec 14 '16 at 15:18 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 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 answered Dec 14 '16 at 10:10 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 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.