Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q*and Q be |pnqn | n ϵ N}). Then which of the following is ALWAYS regular?
Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q*and Q be |pnqn | n ϵ N}). Then which of the following is ALWAYS regular? Correct Answer σ* - P
Key PointsOption 1: P ∩ Q
Regular ∩ context-free is context-free and not regular. (pnqn ∩ p*q* )=pnqn is context-free.
Option 2: P-Q
Regular-context-free
Regular∩ not context-free is not even context-free and not regular.
Option 3: Σ* − P
Σ* − P is an equivalent complement of P, hence regular.
Option 4: Σ* − Q
Σ* − Q is an equivalent complement of Q and It is not even context-free and not regular.
Hence the correct answer is Σ* − P.
Additional Information [ alt="toc closed" src="//storage.googleapis.com/tb-img/production/21/08/toc_closed.png" style="width: 567px; height: 409px;">
