GATE CSE 2021 Set 2 | Question: 36

Question

​​​​​​Consider the following two statements about regular languages:

• $S_1$: Every infinite regular language contains an undecidable language as a subset.
• $S_2$: Every finite language is regular.

Which one of the following choices is correct?

• A. Only $S_1$ is true
• B. Only $S_2$ is true
• C. Both $S_1$ and $S_2$ are true
• D. Neither $S_1$ nor $S_2$ is true

Comments

Both S1 and S2 correct

---

@zxy123 see if we consider the language $L=a^*$ where $\Sigma=\{a\}$ then the language we considered actually becomes $L=\Sigma^*$ which is actually the set of all possible strings using our given alphabet. Now if you think intuitively, you shall be satisfied that, any undecidable language on $\Sigma$ is subset of $L$ actually. But this is not a solid proof. @Deepakk Poonia (Dee) sir’s answer is a solid one… It works on the same idea that most text authors use to proof that there are many many many languages which are not RE.

---

Is Here the Higligheted Part is correct ❓(According to me it is correct please confirm it  bcoz i studied that Turing Recognizable means Recursive Enumerable and Turing Decidable means Recursive Language )

1. Every infinite regular language L has a subset S which is undecidable (Means not recursive ). 
2. Every infinite regular language L has a subset S which is unrecognizable (Means not Recursive emumerable ).
3. Every infinite language L has a subset S which is undecidable (Means not recursive).
4. Every infinite language L has a subset S which is unrecognizable (Means not recursive enumerable ).

Answer 1

Detailed Video Solution: Countability Results in Theory of Computation

$S_1:$ Every infinite regular language contains an undecidable language as a subset.

Cantor’s theorem says that If $S$ is any set then $|S| < |P(S)|,$ where $P(S)$ is the power set of $S.$

So, from this we know that If we have any infinite set $S$ then $P(S)$ is definitely Uncountable (Because remember that a set A is countable if and only if $|A| \leq |\mathbb{N}|,$ where $\mathbb{N}$ is the set of natural numbers).
From this we can say that if $S$ is countably infinite set, then $P(S)$ is uncountable. 

We know that Every language is countable. (Every language $L$ is a subset of $\Sigma^*,$ and $\Sigma^*$ is countable and subset of countable set is countable)
If we have any infinite language $L,$ then it means that we have uncountably many subsets of $L.$ But we know that set of all RE languages is countable. So, due to this we have a subset of $L$ which is Not RE. So, the following statements are true :

1. Every infinite regular language L has a subset S which is undecidable. 
2. Every infinite regular language L has a subset S which is unrecognizable.
3. Every infinite language L has a subset S which is undecidable.
4. Every infinite language L has a subset S which is unrecognizable.

• Here, $(2)$ implies $(1)$ and $(4)$ implies $(3)$ as undecidable set is a proper superset of unrecognizable set. (By undecidable set, I mean Set of all undecidable languages. Similarly, for unrecognizable set. NOTE that if a language is unrecognizable then it is undecidable as well, so, undecidable set is a proper superset of unrecognizable set. Decidable set is a proper subset of Recognizable set because every decidable language is recognizable.)

Watch this Video Solution to Understand Crystal Clearly: Countability Results in Theory of Computation 

Summary of above explanation: 

EVERY language $L$ is Countable. Every language, RE or Not RE, whatever language, is always Countable. 

Set of all RE languages is Countable. Set of all Non-RE languages is Uncountable. 

Now, If $L$ is ANY infinite language, It has uncountable number of subsets (See HERE.). If every subset of $L$ is a RE language, then we can have only countable number subsets of $L$, But $L$ has uncountable number of subsets. That's why $L$ has at least one subset which is Not-RE. 
Actually, $L$ has uncountable number of subsets which are Not-RE. 

---

For regular languages, we can prove statement 1 using pumping lemma as well.

Using the pumping lemma, we find $x,y,z$ such that $xy^nz$ is in language $L$ for every $n,$ and then consider the subset  $S = \{ xy^nz\mid n\in A \}$, where $A$ is any undecidable set of natural numbers. So, $S$ is Not decidable.

$S_2:$ Every finite language is regular.

It is true.

Proof:

Assume that we have a finite language  $L = \{  w_1,w_2,w_3, \ldots, w_n \}$

For $L$ we can write down:

Regular grammar: 

• $S → w_1 \mid w_2 \mid w_3 \mid \ldots \mid w_n $ 

Regular expression:

• $w_1 + w_2 + w_3 + \ldots + w_n$

Hence, $L$ is regular.

---

Edit :

Some more variations :

The statement $S_1$ can be written in Contrapositive manner as following :

$S_1 : $ Every infinite regular language contains an undecidable language as a subset.

Contrapositive of $S_1 :$ If ALL the subsets of a regular language $L$ are decidable then $L$ is finite.

Similarly, we can say, in contrapositive manner, that : 

1. If ALL the subsets of a regular language $L$ are recognizable then $L$ is finite.
2. If ALL the subsets of a language $L$ are decidable then $L$ is finite.
3. If ALL the subsets of a language $L$ are recognizable then $L$ is finite.

Comments

Can someone please explain what @Deepak Poonia sir were trying to imply while writing:
”But we know that set of all RE languages is countable.”, i do know what this means but i am not able to intuitively understand what sir meant.

 

Are they refering that set of all RE language i.e. RL, DCFL, CFL, REC and REL itself are countable?

---

@Yashdeep2000 Once watch this: Countability Results in Theory of Computation

---

Infinite union of countable subsets will get countably infinite,hence there must be some subset which is  uncountable as WKT power set of infinite regular language is uncountable.

Countable U uncountable>uncount.