1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ That's right, $\Sigma^{*} - P$ will always be regular because $P$ is regular and the regular languages are closed under complement. $\endgroup$ – Sam Jones Dec 3 '12 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.