GATE CS 2011 Q24 — Regular and Context-free Languages

To determine which of the given languages is always regular, let us analyze each option using the closure properties of regular and context-free languages (CFLs):

• Option A: $P \cap Q$
  Since $Q \subseteq P$, we have $P \cap Q = Q$. Since $Q$ is a context-free language, it is not necessarily regular (for example, $Q = \{p^n q^n \mid n \ge 0\}$ is context-free but not regular). Thus, $P \cap Q$ is not always regular.
• Option B: $P - Q$
  Using the example given in the question, let $P = p^*q^*$ (regular) and $Q = \{p^n q^n \mid n \ge 0\}$ (CFL). Then:
  $$P - Q = \{p^a q^b \mid a \neq b, a \ge 0, b \ge 0\}$$
  This language is context-free but not regular. Thus, $P - Q$ is not always regular.
• Option C: $\Sigma^* - P$
  The language $\Sigma^* - P$ is the complement of $P$ (denoted as $\overline{P}$). Since $P$ is a regular language, and regular languages are closed under complementation, $\overline{P}$ is guaranteed to be regular.
• Option D: $\Sigma^* - Q$
  The language $\Sigma^* - Q$ is the complement of $Q$ (denoted as $\overline{Q}$). The complement of a non-regular CFL is not necessarily regular (and indeed, context-free languages are not closed under complementation). Thus, $\Sigma^* - Q$ is not always regular.

Therefore, only $\Sigma^* - P$ is always regular.