GATE CSE
First time here? Checkout the FAQ!
x
0 votes
50 views

asked in Theory of Computation by Active (1.3k points)   | 50 views
option d ?
D. Set of all languages over a finite alphabet is countable (finitely or infinitely). Rest all options all incorrect.

1 Answer

0 votes
Best answer
Ans d is correct.

set of all integer is countable. Generate like 1, -1,2,-2... so for a number x. I will take 2x steps to generate it or the corresponding natural number will be 2x. And set of all strings is also countable .

Because (a) is incorrect due to there exist a one to one correspondence between natural no and sigma *

(b) is also incorrect because sigma* multiply as much time it remain same

(c) power set of every countable infinite set is always uncountable set

so d is correct option
answered by (351 points)  
edited by

For countable set, is one-one mapping to integers necessary?

If not, then for option (D), I can map $\sum$* to set of integers as per their lengths.

Top Users Jan 2017
  1. Debashish Deka

    9716 Points

  2. sudsho

    5558 Points

  3. Bikram

    5290 Points

  4. Habibkhan

    5070 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4226 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,449 questions
24,228 answers
53,953 comments
20,373 users