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 :
- Every infinite regular language L has a subset S which is undecidable.
- Every infinite regular language L has a subset S which is unrecognizable.
- Every infinite language L has a subset S which is undecidable.
- 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 :
- If ALL the subsets of a regular language $L$ are recognizable then $L$ is finite.
- If ALL the subsets of a language $L$ are decidable then $L$ is finite.
- If ALL the subsets of a language $L$ are recognizable then $L$ is finite.