# Closure properties of languages

Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always regular?

1. $P \cap Q$
2. $P - Q$
3. $\Sigma^* - Q$
4. $\Sigma^* - P$

Option 1
$P \cap Q = Q$ as $P \subseteq Q$. Thus $P \cap Q$ is context-free.

Option 2
I was not able to generally reason here. I used the example mentioned in the question.
Let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$.
$P - Q = \{a^nb^m | n \neq m\}$ which is not regular but only context-free.

Option - 3
Let $\Sigma = \{ a, b\}$ and $Q = \{ a^nb^n | n \ge 0\}$.
Again $\Sigma^* - Q = \{a^nb^m | n \neq m\}$ which is not regular but only context-free.

Thus, the 4th option must be right, $\Sigma^* - P$ is regular. I am however unable to understand this result intuitively. Could somebody explain?

-
Note $\Sigma^* - Q$ also contains strings not in $a^*b^*$. – Hendrik Jan Dec 29 '12 at 0:26

I got it on further thought. It is trivial. $\Sigma^* - P$ is $P'$, the complement of P and this is regular. I was unnecessarily concentrating on how $Q \subseteq P$ would play a role. It doesn't actually.
That's right, $\Sigma^{*} - P$ will always be regular because $P$ is regular and the regular languages are closed under complement. – Sam Jones Dec 3 '12 at 12:51