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
  • 1
    $\begingroup$ Note $\Sigma^* - Q$ also contains strings not in $a^*b^*$. $\endgroup$ Dec 29, 2012 at 0:26

1 Answer 1

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$
1
  • $\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, 2012 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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