Question

Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?

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

Hint:

In automata theory, the complement of a regular language remains regular, but operations involving context-free languages may not preserve regularity.

Answer 1

The Correct Option is C

Since \( P \) is regular and \( Q \) is context-free with \( Q \subseteq P \), the complement of a regular language \( P \) is always regular. The operation \( \Sigma^* - P \) refers to the complement of \( P \), which remains regular. Thus, this is the operation that is always regular. The other options involve operations on context-free languages, which are not guaranteed to be regular.