Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$. (For example, let $P$ be the language represented by the regular expression $p^*q^*$ and $Q$ be $\{p^n q^n \mid n \in \mathbb{N}\}$). Then which of the following is **ALWAYS** regular?

Let us check the regularity of each given option:

1. **Option (C) $\Sigma^* - P$:**

   • $\Sigma^* - P$ is the complement of language $P$, denoted as $\overline{P}$.

   • Regular languages are closed under complementation. Since $P$ is given to be regular, its complement $\Sigma^* - P$ is always regular.

2. Option (A) $P \cap Q$:

   • Since $Q \subseteq P$, we have $P \cap Q = Q$.

   • $Q$ is given to be a context-free language, which is not necessarily regular (e.g., $Q = \{p^n q^n \mid n \in \mathbb{N}\}$ is context-free but not regular). Thus, $P \cap Q$ is not always regular.

3. Option (B) $P - Q$:

   • For $P = p^*q^*$ and $Q = \{p^n q^n \mid n \in \mathbb{N}\}$, $P - Q = \{p^i q^j \mid i

e j\}$, which is not regular.

4. **Option (D) $\Sigma^* - Q$:**

   • Context-free languages are not closed under complementation, and the complement of a non-regular CFL is generally not regular.

Therefore, (C) is always regular.