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.

Hint:

Regularity depends on recognizability by a finite automaton; finiteness always guarantees regularity.

Answer 1

The Correct Option is C

Step 1: Analyze Statement \(S_1\).
Any infinite regular language contains infinitely many strings. It is possible to select a subset whose membership problem is undecidable (for example, by encoding instances of an undecidable problem into a subset of strings). Hence, an infinite regular language can contain an undecidable language as a subset. Therefore, \(S_1\) is true.

Step 2: Analyze Statement \(S_2\).
Every finite language can be recognized by a finite automaton that explicitly enumerates all its strings (or prefixes). Hence, every finite language is regular. Therefore, \(S_2\) is true.

Step 3: Conclusion.
Since both statements are true, the correct option is (C).