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

asked in Theory of Computation by Loyal (3.1k points)   | 68 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 (393 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 Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2576 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Arunav Khare

    1464 Points

  9. Arjun

    1440 Points

  10. Kapil

    1426 Points

Monthly Topper: Rs. 500 gift card

22,084 questions
28,058 answers
63,274 comments
24,157 users