18 views

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^nq^n \mid n \in N\})$. Then which of the following is ALWAYS regular?

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