edited by
12,980 views
35 votes
35 votes

Consider the following sets:

S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$

S2: Set of all syntactically valid C programs

S3: Set of all languages over the alphabet $\{0,1\}$

S4: Set of all non-regular languages over the alphabet $\{ 0,1 \}$

Which of the above sets are uncountable?

  1. S1 and S2
  2. S3 and S4
  3. S2 and S3
  4. S1 and S4
edited by

4 Answers

Best answer
70 votes
70 votes

Every TM can be encoded with $0$'s and $1$'s, it means that every TM can be represented by a unique binary number.

Let $\Sigma  = \{0,1\}$ then set of all binary strings $= \Sigma^*$. We know that, $\Sigma^*$ is countable $\Rightarrow$ Set of all TM's is countable.

S1:  Set of all recursively enumerable languages over the alphabet $\{0,1\}$

Every Recursively enumerable language have a TM, and set of all TM's is countable. Therefore, set of all Recursively enumerable languages is countable.

S2: Set of all syntactically valid C programs. We can make a one to one equivalence for all valid C programs and all valid TM encodings. Since, the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.

Therefore Set of all syntactically valid C programs are countable.

S3: Set of all languages over the alphabet $\{0,1\}$. It is $2^{\Sigma^*}$ which is uncountable as the power set of an infinite set is uncountable.

S4: Set of all non-regular languages over the alphabet $\{0,1\}$

We know that, set of all languages is uncountable and set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as union of two countable sets cannot make an uncountable set.

Answer is B.

edited by
8 votes
8 votes

Set of all Recursively Enumerable (and hence sets of all regular, context-free, context-sensitive and recursive) languages is countable.

Each such language can be generated by some Turing Machine. Each Turing Machine can be encoded into a finite-length bit string. And set of all finite languages is countable.

=> S1 is countable.

=> S2 is countable. (Programming Language C is CSL. https://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar)

 

Not partially decidable languages (ie outside RE) are uncountable.

=> S3 is uncountable; as the set of all languages includes Not partially decidable languages. Same for S4.

Option B.

4 votes
4 votes

Note:- Recursively Enumerable language means we can put all string of that language into one to one correspondence with natural no(1,2,3,4,5,6...).  Any language which is enumerable(all strings of that language can be generated by some procedure within infinite time) is also countable.  and any language which is uncountable cannot be recursively enumerable.

S1) Set of all recursively enumerable languages over the alphabet {0,1}

This is countable because We will be able to generate all recursively enumerable languages within infinite time using some procedure.

S2) Set of all syntactically valid C programs

This is countable. It is equivalent to say that set of all Turing machines are countable or not. Just like all Turing machines can be generated one by one, all c program can be written one by one.

S3) Set of all languages over the alphabet {0,1}

This is uncountable. Since the set of all languages will contain "regular language, context-free language, recursively enumerable language and non-recursively enumerable language".  But the set of non-recursively enumerable languages are uncountable...

S4) Set of all non-regular languages over the alphabet {0,1}

This is uncountable. since the set of non-regular languages will also contain set of non-recursively enumerable languages which are uncountable, and moreover set of all languages are uncountable but set of recursively enumerable languages are countable that implies set of non-recursively enumerable languages must be uncountable.

So option B is correct.

edited by
4 votes
4 votes

$\color{red}{\text{Detailed Video Solution, with Proof:}}$ https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=2913s  

S1: For EVERY alphabet, Set of all recursively enumerable languages is countable.

To show that a set $S$ is countable, we can show that there exists a surjective function from some countable set to set $S.$

Set of all Turing machines is countable, & we can create a Surjective function $f$ from set of all Turing machines to set of all RE languages by mapping any Turing machine $T$ to $L(T)$ i.e. $f(T) = L(T).$ This mapping is surjective. So, set of all recursively enumerable languages is countable.

Detailed Video Explanation of this proof is HERE.


S2: Set of all syntactically valid C programs is countable.

In fact, Set of all programs is countable because every program is a finite sequence of statements. Inside a computer, every program is stored as some binary string of finite length. So, set of all programs is the same as the set of some finite length binary strings which is a countable set. 

Detailed Video Explanation of this proof, with more variations is HERE.


S3: For EVERY $\Sigma,$ the set of all languages is uncountable.

The set of all languages over $\Sigma$ is the powerset of $\Sigma^*$ i.e. $P(\Sigma^*).$

Proof:

By Cantor’s theorem, we know: If $S$ is ANY infinite set, then $P(S)$ is always uncountable. (Or we can say, NO infinite powerset is countable.)

Since, for every $\Sigma$, $\Sigma^*$ is infinite, hence, $P(\Sigma^*)$ is uncountable.

Learn Cantor’s Theorem & its Consequences HERE.


S4: For EVERY alphabet, Set of all non-regular languages is uncountable.

We know the set of all regular languages is countable, But the set of ALL languages is uncountable, So, set of all non-regular languages is uncountable.

Detailed Video Explanation of this proof is HERE.


Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared  

Answer:

Related questions