1
$\begingroup$

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!

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

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
1
  • 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$ Oct 12, 2017 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.