Question

Consider two languages A and B where A is a context free language and B is a regular language. Show that the set difference, A-B, must also be context free.

Also show that B-A may not be context free

Answer 1

Context free language is a language that is accepted by a context free grammar and it is processed by pushdown automata. It is described using context free grammar. A language is said to be context free if and only accepted by push down automata. A context free language is closed under union,concatenation,closure and homomorphism.

Regular language is a language that are expressed using regular expression.It is also expressed using deterministic or non-deterministic finite automata or state machine. The closure properties of regular languages include union, concatenation, intersection, kleen closure and compliment.

Every regular language is accepted by finite automata , Every finite automata is automatically a pushdown automata which ignores stack., so we can conclude that every regular language is also a context free language.

A and B are the languages given in the question. A is a context free language and B is a regular language.

Answer to first question

The intersection of context free language and regular language is context free.

Here we have to prove that A-B(set difference) is context free.

we can write A - B = A B' where B' is compliment of B.

B' is regular because all regular languages are closed under compliment. Therefore A   B' is a context free by the above defined law. i.e the intersection of context free language and regular language is also context free, because A B.

So A - B is context free.

Answer to second question

Show that B - A may not be context free.

We can write, B - A = B A' , but A' is not context free because context free languages are not closed under compliment. So that B - A is need not be context free.