in Theory of Computation recategorized
2,503 views
2 votes
2 votes
Which of the following statements is/are not correct?
(P) The class of all Turing Machines is countably infinite
(Q) The class of all DCFL's is countably infinite
(R) The class of all formal languages is uncountably infinite
(S) The set of all primes is countably infinite

  1. Only R
  2. Only R and S
  3. All are incorrect except P
  4. None of the above
in Theory of Computation recategorized
2.5k views

9 Comments

Does "The class of all formal languages" corresponds to all R.E. languages?
0
0
Yeah even  I've  same doubt
0
0

@Ayush Upadhyaya no. If so it would have been countably infinite. A formal language also includes non recursively enumerable languages. 

3
3
thank you sir :). Got my mistake.
0
0

@Arjun sir

Formal langauges = (Class of all RE languages ) union (Class of all Non - RE languges)

as Class of formal langauges is uncoutabe and class of RE languages is countably infinite

this means (Class of Non - RE languges) is also uncountable otherwise All formal languages will be countable

M i right sir ?

0
0
Great paper. Will you make 1 more paper?
8
8
..
0
0

@Arjun 

Sir, I request to make more mock test of this level for GATE 2020

(Every question in this paper giving better clearity of concepts )

1
1
(P) The class of all Turing Machines is countably infinite
(Q) The class of all DCFL's is countably infinite

is this 2 stmts meant that subset of RE/DCFL is countably infinite? like 2^RE , 2^CFL
0
0

2 Answers

0 votes
0 votes

All statements are correct.

D is the answer.

edited by

4 Comments

Set of prime numbers is a  subset of natural numbers and set of natural numbers is countably infinite, so S is also correct
2
2
The rule you are talking about holds if the subset is finite.

An infinite subset of a countable infinite set maybe uncountable infinite.
0
0
edited by

@gmrishikumar Any set is countably infinite if you can make one-to-one correspondence of its elements with natural numbers.

In case of prime numbers, you can say that -:

1st prime = 2

2nd prime = 3

3rd prime = 5.............and so on.

Thus, they are countably infinite.

0
0
Updated the answer.
0
0
0 votes
0 votes
non recursively enumerable languages doesn't fall under formal language...

http://zasoby.open.agh.edu.pl/~11sustrojny/en/chomsky-classification/index.html

Chomsky created 4 classes we should obey Chomsky i guess

so class of all formal languages is countably infinite only..

and i didn't find anywhere its written as non r.e. is formal language... everywhere its 4 class upto r.e. only
Answer:

Related questions