Let \(P\) be a regular language and \(Q\) be a context-free language such that…

GATE · 2011 · CS · Computer Science & IT

Let PP be a regular language and QQ be a context-free language such that Q⊆PQ \subseteq P. (For example, let PP be the language represented by the regular expression p∗q∗p^*q^* and QQ be {pnqn∣n∈N})\{p^nq^n \mid n \in N\}). Then which of the following is ALWAYS regular?

  1. A.

    P∩QP \cap Q

  2. B.

    P−QP -Q

  3. C.

    Σ∗−P\Sigma^*-P

  4. D.

    Σ∗−Q\Sigma^*-Q

Attempted by 164 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…