[Solved]: Closure properties of languages

Problem Detail: 

Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always regular?

1. $P \cap Q$
2. $P - Q$
3. $\Sigma^* - Q$
4. $\Sigma^* - P$

Option 1
$P \cap Q = Q$ as $P \subseteq Q$. Thus $P \cap Q$ is context-free.

Option 2
I was not able to generally reason here. I used the example mentioned in the question.
Let $P = a^*b^* $ and $Q = \{ a^nb^n | n \ge 0\}$.
$P - Q = \{a^nb^m | n \neq m\}$ which is not regular but only context-free.

Option - 3
Let $\Sigma = \{ a, b\}$ and $Q = \{ a^nb^n | n \ge 0\}$.
Again $\Sigma^* - Q = \{a^nb^m | n \neq m\} $ which is not regular but only context-free.

Thus, the 4th option must be right, $\Sigma^* - P$ is regular. I am however unable to understand this result intuitively. Could somebody explain?

Asked By : Abhijith Madhav

Answered By : Abhijith Madhav

I got it on further thought. It is trivial. $\Sigma^* - P$ is $P'$, the complement of P and this is regular. I was unnecessarily concentrating on how $Q \subseteq P$ would play a role. It doesn't actually.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7118

3.2K people like this

 Download Related Notes/Documents