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

enter image description here

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.


1 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)


$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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.