# Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$

This is my take :

Epsilon ---> 1

0 --> 2

01 ---> 3

10 ---> 4

11 ---> 5

001 ---> 6

010 ---> 7

. . .

So therefore we can count them.

But based on this video : https://www.youtube.com/watch?v=oe-ZAJQz9Cc&index=5&list=PLsFENPUZBqiqbnD-WatYxUhRWLMNDoMun

They should not be countable, but i did not understand that video, the guy says all possible languages over $\{0,1\}^{*}$ are uncountable!

• You say you can count them, so what makes you doubt that this set is not countable? – fade2black Sep 28 '17 at 10:47
• Because based on this video they are uncountable, but i dont get it : youtube.com/… – Richard Jones Sep 28 '17 at 10:48

The language $$L= (0+1)^*$$ (the set of all strings over $0$ and $1$) is countable. Furthermore, any subset of $L$ is also countable. However, the set of all sublanguages of $L$ $$S = P(L) = \{M \mid M \subseteq L\}$$ (a set of sets in fact) is not countable. This video proves this using the diagonalization argument.
$S$ and $L$ are two different sets. In fact, $L$ is a member of $S$.
• Note that your definition of $L$ is just a long way of writing $L = (0+1)^*$ (analogous to saying "Let $S = \{x\mid x\in T\}$"). – David Richerby Oct 12 '17 at 18:05