Question 9145 – GATE 2008
December 19, 2023Question 14303 – Theory-of-Computation
December 19, 2023Question 14297 – Theory-of-Computation
- Consider the following two statements about regular languages:
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.
Which one of the following choices is correct.?
Correct Answer: B
-
S1 is true. We can solve this intuitively.
Suppose L=(a+b)* i.e, sigma*
We know that this is a regular language and any language is subset of this language.
As we know so many undecidable languages (not recursive languages) exist, hence S1 is true.
Take another example:
L=a* which is regular and infinite.
Take its subset L1=an | n> 0 and n is a set such that it cannot be generated by any algorithm
I.e, n is a set of natural numbers which does not have any algorithm which can generate this
So L1 is a undecidable language.
L2 is true as every finite language is regular.