in Theory of Computation edited ago by
9,274 views
30 votes
30 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
in Theory of Computation edited ago by
by
9.3k views

3 Answers

57 votes
57 votes
Best answer

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

4 Comments

@srestha maam, how can be set of c programs be countable ?..

because it would be similar to the problem finding all possible languages for given set of symbols !  

 

0
0
When we talk about the set of all non-regular languages, that includes languages that are not RELs as well, so is that another reason for set of all non-regular languages to be uncountable ?
0
0

@Rutuja Desai Set of all non-regular languages include NOT RE languages also, which are uncountable. Upto RE language, it is countable. Beyond that uncountable.

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

1 comment

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

 

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

0
0
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 Comments

No, that is correct only. To make it precise you should say that set of non-recursively enumerable languages is uncountable because the set of languages is uncountable and set of recursively enumerable languages is countable. Now, all the elements of this uncountable set is present in the non-regular language set making it uncountable.
2
2
Plz tell me

1)Can  the set of recursive language, CFL or Regular language be countable?

2) Why set of real number always uncountable (if some range is given, still it is uncountable)?
0
0
Sir, Is the S4 correct now? Is it necessary to take the support of the statement "set of all languages are uncountable" to prove "set of all non-recursively enumerable languages are uncountable". Since every non-recursively enumerable language is uncountable so set of all non-recursively enumerable languages will also be uncountable. can we say like this?
0
0