TIFR CSE 2023 | Part B | Question: 2

Question

Which of the following is true about the set of regular languages and the set of recursively enumerable languages over a finite alphabet $\Sigma?$ 

• A. The set of regular languages is countable while the set of recursively enumerable languages is uncountable.
• B. The set of regular languages is uncountable while the set of recursively enumerable languages is countable.
• C. The set of regular languages and the set of recursively enumerable languages are both countable.
• D. The set of regular languages and the set of recursively enumerable languages are both uncountable.
• E. The set of regular languages is countable while whether the set of recursively enumerable languages is countable or not is not known and is a longstanding open problem.

Answer 1

Let $\sum =\left \{ 0,1 \right \}$ be alphabet.

$\sum^{*}$= Set of all strings from alphabet

L=set of all languages , It is actually power set of $\sum^{*}$ .

now $\sum^{*}$ is countable set as there can be one-to-one corresponding between $\sum^{*}$ and natural number.

Now  L is an uncountable set as from cantor theorem, if S is Countably infinite set then P(S) is uncountable. Here $\sum^{*}$ is countable set so it’s power set is L so ,L is uncountable.

So set of all language is uncountable.

---

set of all language ={set of all RE language} $\cup$ {set of all Non RE language}  [RE means Recursively enumerable]

Now , We know that set of all RE language is countably infinite as there exist a TM for an RE language and set of turing machine is countable.

Now as the  Set of all RE language is countable , now to make the set of all language uncountable , the set of Non RE language must be uncountable.

So set of all non recursive enumerable language is uncountable . 

So,set of all RE language is countable .

Now, set of all Regular language are subset of set of all  RE language . which is countable .

and we know subset of countable set is also countable so, set of all regular language is also countable .

So correct option is (C).

https://math.stackexchange.com/questions/551630/subset-of-a-countable-set-is-itself-countable

https://en.wikipedia.org/wiki/Cantor%27s_theorem

https://gateoverflow.in/378523/self-doubt?state=edit-378531