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!

  • $\begingroup$ You say you can count them, so what makes you doubt that this set is not countable? $\endgroup$ – fade2black Sep 28 '17 at 10:47
  • $\begingroup$ Because based on this video they are uncountable, but i dont get it : youtube.com/… $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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\}$"). $\endgroup$ – David Richerby Oct 12 '17 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.