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

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

---

for those confused for option b a counter example is
p =   ∑* is a regular language
since  ∑* contains all possible string over ∑ and thus
∑* - P may be CFL may be CSL may be Regular we are not exactly sure thus
P - Q is regular is incorrect

---

P - Q = P ^ Q^C

(sigma)* - P = (sigma)* ^ P = regular are closed under intersection

(sigma)* - Q = (sigma)* ^ Q = CFL are not closed in intersection

Answer 1

Correct Option: C

complement of regular Language is regular

Comments

Beautifully explained @Shailendra. Thanks :)

---

CFl are closed under Intersection with regular set means that CFL intersection reg language are CFLs

 

---

Regular - CFL is always CSL.

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?