GATE CS 2007 Q7 — Regular and Context-free Languages

Let us analyze each option to determine its correctness:

• Option A: Every subset of a regular set is regular.
  False. Consider the regular language $L = a^*b^*$. Its subset $L' = \{a^n b^n \mid n \ge 0\}$ is non-regular.
• Option B: Every finite subset of a non-regular set is regular.
  True. Every finite set is regular because we can always construct a DFA or write a regular expression for any finite set of strings. Since any finite subset of a non-regular set is, by definition, a finite set, it must be regular.
• Option C: The union of two non-regular sets is not regular.
  False. Let $L_1 = \{a^n b^n \mid n \ge 0\}$ and its complement $L_2 = \overline{L_1}$. Both are non-regular, but their union $L_1 \cup L_2 = \Sigma^*$ is regular.
• Option D: Infinite union of finite sets is regular.
  False. Any language (including non-regular ones) can be represented as an infinite union of singleton (finite) sets. For example, $\{a^n b^n \mid n \ge 0\} = \bigcup_{n=0}^{\infty} \{a^n b^n\}$ is non-regular.