i am asking myself the following question:
Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right? but I do not know how to prove it.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.)
See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.
$\begingroup$
$\endgroup$
It might be context sensitive as well...
example:-
let
L1= ${\{a^n b^n c^m | n>0, m>0\}}$
and
L2=${\{a^m b^n c^n | m>0, n>0\}}$
Here L1 and L2 are context free but L1-L2 will be
L1-L2 = ${\{a^n b^n c^m | n>0, m>0 \space \& \space n \neq m\}}$
which is NOT context free.
