Question

Let P be a regular language and Q be a context-free language such that Q ⊆ P. Then which of the following is always regular?

• A. P ∩ Q
• B. P − Q
• C. Σ* − P
• D. Σ* − Q

Hint:

Regular languages are closed under intersection with other languages, including context-free languages.

Answer 1

The Correct Option is A

The intersection of a regular language P with any language (including a context-free language Q) is always regular. This is because regular languages are closed under intersection with other languages, including context-free languages. Therefore, P ∩ Q will always be a regular language.