GATE CS 1998 Q2.6 — Regular and Context-free Languages

We need to identify the false statement among the given options.

• Option (a): Every finite subset of a non-regular set is regular.
  True. Any finite language is always regular because we can construct a Finite Automaton or write a regular expression for it. Since any finite subset of any set is finite, it must be regular.
• Option (b): Every subset of a regular set is regular.
  False. Consider the regular language $R = \Sigma^* = \{a, b\}^*$. Every language over $\{a, b\}$ is a subset of $R$. However, we know that non-regular languages exist (for example, $L = \{a^n b^n \mid n \ge 0\}$). Since $L \subseteq R$ and $L$ is not regular, this statement is false.
• Option (c): Every finite subset of a regular set is regular.
  True. As established, any finite set is regular. Thus, any finite subset of a regular set is regular.
• Option (d): The intersection of two regular sets is regular.
  True. Regular languages are closed under the intersection operation.

Therefore, statement (b) is false.