Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using pumping lemma?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Are you aware that CFL is not closed under complementation? Perhaps you can use that (I'm not sure if you consider this as usage of the pumping lemma, since the standard proof of the latter does use the pumping lemma) $\endgroup$– ShaullAug 10, 2013 at 11:11
-
2$\begingroup$ What have you tried? How would you apply the Pumping lemma without a concrete language in hand? $\endgroup$– Raphael ♦Aug 11, 2013 at 11:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Hendrik Jan gives a nice complete answer. If you're looking for a more abbreviated proof, without mention of Turing machines, you can prove it fairly easily, starting with the assumption that $CFL$ is not closed under complementation.
We know that there exists $L\in CFL$ such $\overline{L} \not \in CFL$, that is, its complement is not context free. But $\Sigma^* \setminus L = \overline{L}$. Since $\Sigma^*$ and $L$ are both context free, this shows $CFL$ is not closed under difference.
-
1$\begingroup$ Without pumping lemma, as asked? Your example $\overline{L}$ most probably is shown non-context-free by pumping, so you are a little cheating here :) My answer is way over the top, but I think it avoids pumping. $\endgroup$ Aug 16, 2013 at 20:17
-
3$\begingroup$ I never use the pumping lemma. The pumping is used to prove that a given language $L$ is not context free. You only use it when you actually know what $L$ is. I never need to use the pumping lemma to show that $\overline{L}$ is not context free, since I take as an assumption that such an $L$ exists. My proof just shows that not being closed under difference is a direct consequence of not being closed under complement. $\endgroup$– jmiteAug 16, 2013 at 20:27
$\begingroup$
$\endgroup$
3
Yes I believe it is possible to prove such a non-closure property without pumping a specific example language.
As noted in the comments, complement $\Sigma^* - L$ is a special form of difference. It turns out that complementation is an extremely powerful tool used with context-free languages. One can show that computation histories of Turing machines can be specied as complements of context-free languages. This seems to originated from J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings of Symposia in Applied Mathematics, Vol. 19, AMS, 1967, 42-51.
A computation history (for a fixed TM $M$) is a string of the form $x\$C_0\$C_1\$\dots\$C_n$ where $x$ is an input string, $C_0$ is the initial configuration of $M$ on $x$, meaning a string of the form $q_0x$ where $q_0$ is the initial state, $C_n$ is a final configuration (with a final state) and each pair of consecutive $C_{i-1}\$C_i$ represents a single step of TM $M$.
The language of those strings is the complement of a context-free language.
What is CFL would be closed under complement? Then the context-free languages would be equal to the languages accepted by Turing Machines: the languages of valid computations would be context-free, and from this we can find their prefixes or the accepted inputs of the TM. I do think that is a contradiction without the pumping lemma. We know there are more TM accepted languages than CF languages by complexity or decidability arguments.
answered Aug 13, 2013 at 21:48