Regular Language - Context Free Language

Question

I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question

Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\sum^*$, which of the following about the langauge $R=\overline{A}-B$  is  $TRUE?$

a. $R$ is necessarily $CFL$ but $not$ necessarily $regular$

b. $R$ is necessarily $regular$ but $infinite$

c. $R$ is necessarily $non$ $regular$

d. $None$

e. $\phi$

---

Now I have approached this problem in 2 ways and I am getting 2 different results.

---

The first way in which I have approached is that, since $A'-B=A'\cap B'$, so it is $Reg$ $L$ $\cap$ $CSL=CSL$ , so answer is $NONE$

---

On the other hand I have think of it like this, since $A$ is $Regular$ it's complement is also $regular$, Now we know that

So $regular$ $language$ being a subset of $CFL$ must give us $\phi$ when we are doing $A'-B$, so this time I am getting $\phi$ as answer

---

My question is which of my approach is correct? Is the first one correct? If so, then why the second one is wrong?

Or is the second one correct? If so then why the first one is wrong?

---

I believe that the second method shown by me is wrong as say we have a regular language  $A=\phi$, so $\overline{A}=\sum^*$ and say $B=a^nb^n$

then $\overline{A}-B=a^xb^y$, where $x\neq y$, so it is a $CFL$ but not $\phi$.

So where did I went wrong in my second proof using $Chomsky$ $hierarchy?$

---

Downvoters(if any) please mention the reason of downvote in comment. Thank you.

Answer 1

Your second method to arrive at $\phi$ is bogus - consider the case where $B$ is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages.

The correct answer is d. None (you can't say anything)

Because

$R=\overline{A}-B = \overline{A \bigcup B} $

Since $A \bigcup B$ is clearly a $CFL$, this answer applies which states that the complement of a $CFL$ is not necessarily $CFL$ itself ($CFL$ are not closed under complement).