The Gateway to Computer Science Excellence
+21 votes

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
in Theory of Computation by Veteran (52.2k points)
edited by | 3.2k views

3 Answers

+27 votes
Best answer

(b) Set of all languages over $\Sigma$ is uncountable.


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. 

by Veteran (431k points)
edited by
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 ?
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.
@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!:)
+25 votes
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.
by Active (1.8k points)
0 votes
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.
by Active (1.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,299 answers
104,993 users