GATE CSE 1997 | Question: 3.4

Question

Given $\Sigma=\{a,b\}$, which one of the following sets is not countable?

• A. Set of all strings over $\Sigma$
• B. Set of all languages over $\Sigma$
• C. Set of all regular languages over $\Sigma$
• D. Set of all languages over $\Sigma$ accepted by Turing machines

Comments

Set of all non regular language is uncountable ??

---

@anas_2908, Yes, Set of all non-regular languages is Uncountable.

Set of regular languages is Countable. But Set of all languages is Uncountable. So, Set of all non-regular languages is Uncountable.

Detailed Video Solution of this question: Detailed Video Solution, with Proof  

Countability Complete Course Playlist, with COMPLETE coverage of every topic, with Proof: 

https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared 

Answer 1

Correct Option: B

Set of all languages over $\Sigma$ is uncountable.

Ref: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec05.pdf

---

Power set of an infinite set is uncountable. Set of languages over $\Sigma$ is the power set of set of strings over $\Sigma$ which is an infinite set. Hence the set of languages becomes an uncountable set. 

Comments

@Arjun Sir here best ans is crossed , what is ans here :o

---

@Sreshtha Don't know who have crossed it.I uncrossed it.

Arjun sir had given a reference of  MIT though someone thinks it is wrong!:)

---

Arjun sir plz send me important set of problems from each subject

Answer 2

A) The set Σ* is countable because each element of this set can be generated in the following order (called proper order):

Let Σ={a,b}. So, proper order = a,b,aa,ab,ba,bb,aaa,aab....

D) The set of all languages accepted by TMs is the set of all TMs basically, which is countable because each TM can be represented by a binary string and each binary string can be obtained in a proper order (as stated above) and checked whether it's a TM or not.

C) The set of all regular languages is a subset of the set of all recursively enumerable languages. And a subset of a countable set is always countable. This is because all the elements of the countable set can be written in a specific order and each of that element can be checked for its membership in the other set.

B) The set of all languages is uncountable, according to Cantor's Diagonalisation Proof.

Comments

You could include this http://dspace.bracu.ac.bd/xmlui/bitstream/handle/10361/523/Vol%201%20No%202.14.pdf?sequence=1&isAllowed=y

---

“And a subset of a countable set is always countable.”

Counter example: Sigma * is countable but subset of Sigma * (i.e. set of all possible languages is uncountable).

@Vishal Goel

---

Isn't set of all languages and set of all languages accepted by Turing machine same thing.

Is there some language that is not accepted by a Turing machine?

---

@Anupreet13 Subset of Σ* will be a language not a set of languages , any set of languages will be subset of power set of Σ*(because it is the set of all languages).

Answer 3

for option (a)

 All languages generated by Turing machines, are countable. This is because they are all subsets of Σ* and Σ* itself is countable. However, there are uncountably many languages so (b) is uncountable.

Comments

1. How Set of all languages over Σ accepted by Turing machines will be subset of Σ* (because subset of Σ* will be a language not a set of language)?
2. Set of all languages over Σ accepted by Turing machines will subset of power set of Σ* because it is the set of all languages and any set of languages will be its subset .

Answer 4

opt A:set of all strings are finite.so it is countable

opt C:set of all regular languages is always countable

opt D:set of all languages accepted by Turing machine is countable.

opt A: By diagonalization method, we can prove that set of all languages are not countable.

Comments

nice

---

 

opt A:set of all strings are finite.so it is countable

                 This is an infinite set.