The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2k 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
asked in Theory of Computation by Veteran (59.6k points)
edited by | 2k views

3 Answers

+22 votes
Best answer

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

answered by Veteran (363k points)
edited by
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 ?
+14
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!:)
+15 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.
answered by Active (1.5k 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.
answered by Active (1k 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

42,599 questions
48,601 answers
155,674 comments
63,743 users