edited by
813 views
3 votes
3 votes

Choose the correct statement:

  1. The set $[0,1]$ can be efficiently enumerated.
  2. The set of all formal languages can be efficiently enumerated.
  3. All real numbers can be efficiently enumerated.
  4. Set of all finite automata can be efficiently enumerated.
edited by

1 Answer

2 votes
2 votes
1:) i dont know what is the meaning of[0,1]..if it is all real nos between 0 to 1 then yes we cant design an enumerator for this..as it is uncountable

2:)we know that set of all strings generated by an alphabet is countable....also set of all languages is not countable(can be proved using diagnolisation method)...so this statement is also false

3:)obviously no...we need some method to enumerate one to one correspondence of all real nos with natural nos...but it is not possible...between 0 and 1 only we have so many real nos which will literally eat up all natural nos
(Now i dont know the difference between option 1 and this option)

4:)yes....since sigma star is countable...and we know that set of all TM is a subset of sigma star....means subset of a countable set is countable....so this is true...

final conclusion:....b and c are definitly wrong.....d is true...i dont know what is a option means...

Related questions