GATE CSE 2011 | Question: 24

Question

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?

• A. $P \cap Q$
• B. $P-Q$
• C. $\Sigma^*-P$
• D. $\Sigma^*-Q$

Comments

Is it only for regular languages exclusively to follow that ∑* – P = P` (where P is a regular language and P` is the complement of P)? OR

1]  ∑* – P = P` (where P is a CFL and P` is the complement of P)?

2]  ∑* – P = P` (where P is a CSL and P` is the complement of P)?

Are above assumptions 1 and 2 also correct?

---

1st is wrong and 2^nd one is correct,

---

@ASNR1010 It’s because CFL is not closed under complementation [reason for option 1 is incorrect] while CSL is closed under complementation [reason for option 2 is correct] , right? 

---

yup, because you’re checking the closure after all.

Answer 1

Correct Option: C

complement of regular Language is regular

Comments

This is the correct explanation of option b.

---

Beautifully explained @Shailendra. Thanks :)

---

But CFl are closed under Intersection with regular set so why not option A is correct too?

Answer 2

The expression ∑* – P represents complement of P which is a regular language. Complement of Regular languages is also regular. Then a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its accepting states with its non-accepting states.

Comments

Is it only for regular languages exclusively to follow that ∑* – P = P` (where P is a regular language and P` is the complement of P)? OR

1]  ∑* – P = P` (where P is a CFL and P` is the complement of P)?

2]  ∑* – P = P` (where P is a CSL and P` is the complement of P)?

Are assumptions 1 and 2 also correct?