2.3k views

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

1. Set of all strings over $\Sigma$
2. Set of all languages over $\Sigma$
3. Set of all regular languages over $\Sigma$
4. Set of all languages over $\Sigma$ accepted by Turing machines
edited | 2.3k views

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

edited
0
Sir ,

if it was a set of all Finite Automatons over {0,1} , what would the answer be ?
As each regular expression can be represented by a FAs and as set of regular expressions are countable, set of FAs are also countable .

Is my reasoning correct ?
+16
Set of all turing machines are countable and set of all languages are uncountable therefore there are some language that are not turing recognizable. [this is one of the way to proof existence of Not RE language, there are 2-3 other ways as far as i know.]

@Harsh, As set of TM are countable => set of FA are countable.
0
@Arjun Sir here best ans is crossed , what is ans here :o
+1
@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!:)
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.
0
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.

1
2