which of the following is always regular

Question

Let P be a regular language and Q be a context free language such that Q ⊂ P.

Which of the following is always regular ?

(A) P ∩ Q

(B) P-Q

(C) Σ*    - P

(D) Σ*  - Q

Comments

option C) Complement of Regular language is Regular

---

Pardon my ignorance , but is not it P proper subset of Q ( as Regular languages are subset of CFL )

---

Regular languages are subset of CFLs. But not every regular language is a subset of every CFL. The first statement is with respect to language families.

Answer 1

Option C. As Regular languages are closed under complement

A. $P \cap Q$ won't be regular, if $P = \Sigma^*$ and $Q$ is a CFL but not regular.

B. $P-Q$ won't be regular when $P = \Sigma^*$ and $Q$ is a CFL as this will be $\bar Q$ and CFL complement need not even be CFL.

D. This is CFL complement and this need not even be CFL.

Comments

Can someone give counter example for first option

---

That is given rt?

---

p=(a+b)* it is regular

q={a^nb^n/n>=1} it is dcfl

p∩q=(a+b)*∩{a^nb^n/n>=1}

      ={a^nb^n/n>=1} this is cfl but not regular