search
Log In
26 votes
5.6k 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
in Theory of Computation
edited by
5.6k views

4 Answers

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


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 ?
27
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.
1
@Arjun Sir here best ans is crossed , what is ans here :o
2
@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!:)
33 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.
1 vote
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.
0 votes
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.

Related questions

44 votes
6 answers
1
15.2k views
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$
asked Sep 29, 2014 in Theory of Computation Kathleen 15.2k views
19 votes
1 answer
2
3.4k views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
asked Sep 29, 2014 in Theory of Computation Kathleen 3.4k views
19 votes
4 answers
3
2.6k views
Consider the grammar $S \rightarrow bSe$ $S \rightarrow PQR$ $P \rightarrow bPc$ $P \rightarrow \varepsilon$ $Q \rightarrow cQd$ $Q \rightarrow \varepsilon$ $R \rightarrow dRe$ $R \rightarrow \varepsilon$ where $S, P, Q, R$ are non-terminal symbols with $S$ being the start symbol ... $i, j, k, m$? Find the smallest string that has two parse trees.
asked Sep 29, 2014 in Compiler Design Kathleen 2.6k views
21 votes
2 answers
4
5.5k views
Given $\sqrt{(224)_r} =(13)_r$. The value of the radix $r$ is: $10$ $8$ $5$ $6$
asked Sep 29, 2014 in Digital Logic Kathleen 5.5k views
...