Let \(P\) be a regular language and \(Q\) be a context-free language such that…
2011
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\)
Attempted by 86 students.
Show answer & explanation
Correct answer: C
Answer: Σ* - P is always regular.
Reason: Regular languages are closed under complement. Since P is regular, its complement Σ* - P is also regular.
P ∩ Q: Because Q ⊆ P, this intersection equals Q. Q may be a context-free language that is not regular (for example, Q = {p^n q^n}), so the intersection is not necessarily regular.
P - Q: This is P ∩ (Σ* - Q). It can fail to be regular. For instance, let Σ = {p,q}, P = Σ*, and Q = {p^n q^n}. Then P - Q = Σ* - Q, which is not regular.
Σ* - Q: The complement of a context-free language need not be regular. Using the same example Q = {p^n q^n} shows Σ* - Q can be nonregular.
Conclusion: Only Σ* - P is guaranteed to be regular, because regular languages are closed under complement; the other expressions can be nonregular as shown by counterexamples.
A video solution is available for this question — log in and enroll to watch it.