Multiple choice

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?

  1. $P \cap Q$

  2. P - Q
  3. $P-Q$
  4. $\Sigma^*-Q$
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

$\Sigma^*-P$ is the complement of P so it is always regular, since regular languages are closed under complementation

Keep practicing — related questions