[TOC] Check given set is countable

Question

Given that

S1 :Set of all regular languages over Σ

S2 : Set of all languages over Σ accepted by Turing machines

then S1 and S2 respectively are:

a) countable, countable

b) uncountable, countable

c) countable, uncountable

d) uncountable, uncountable

Answer 1

Answer (a) Both are countable.

Following sets are countable

(1) Set of all strings over Σ

(2) Set of all regular languages over Σ

(3) Set of all languages over Σ accepted by Turing machines

BUT

Set of all possible languages over Σ is NOT countable

Comments

yup I  missed it

Answer 2

S1 is uncountable S2 is countable ????

Answer 3

Answer should be A , Countable and Countable as we can associate some correspondance relation with Natural Number.

Comments

"with Natural number"

---

Yes sir! it is subconsious in my mind..just some writing mistakes always happen...kinda forget always natural and real number. :(