edited by
12,242 views
38 votes
38 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
edited by

5 Answers

Best answer
47 votes
47 votes

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. 

edited by
46 votes
46 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 votes
1 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.
0 votes
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.
Answer:

Related questions

64 votes
64 votes
8 answers
1
Kathleen asked Sep 29, 2014
37,235 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^*$$...
24 votes
24 votes
1 answer
2
Kathleen asked Sep 29, 2014
14,258 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$...
27 votes
27 votes
2 answers
4
Kathleen asked Sep 29, 2014
11,706 views
Given $\sqrt{(224)_r} =(13)_r$.The value of the radix $r$ is:$10$$8$$5$$6$