Background: I was in class and heard this sentence from my professor "Well if you take a non context free language and add $2$ words to it then it will stay non context free".
Now I was trying to understand why does this happen always and how can I prove something like this, If we take the language $L=\{ a^nb^nc^n:n\ge0\}$ which isn't context free, and add $a,b$ to it this way: $\{a^nb^nc^n:n\ge0\}\cup\{a\}\cup\{b\}$, I can intuitively see that there's just a simple difference where this language accepts $a$ and $b$ words.
But my problem is how do I prove it formally for all languages, if this was about regular languages, since they're closed under intersection, I could assume that the new language with a couple more words is regular, take the intersection and get the irregular language I started with and reach a contradiction proving it's irregular.
But context free languages aren't closed under intersection, so I can't just say lets take $L\cap \{a^nb^nc^n:n\ge0, a, b\}=L$ it's non context free so $\{a^nb^nc^n:n\ge0, a, b\}$ is not context free.
I would appreciate any help of how to prove this formally for non context-free languages, and any feedback on my attempts is really appreciated.
Thanks in advance.
2 Answers
Indeed you cannot use the general closure under intersection, because it does not hold for context-free languages. So we proceed in a different way. Suppose you add a finite language $F$ to a non-context-free language $L$ and the result $K= L\cup F$ is context-free. Here $$L= (K- F) \cup (L\cap F).$$ $(K-F)$ is context-free, because $K$ is and $F$ is finite. $(L\cap F)$ might look more complicated at first sight, because $L$ is non-context-free; however, since $F$ is finite, also $(L\cap F)$ is finite and thus it is context-free. So we obtain $L$ as the union of a context-free and a finite language, which means that $L$ should also be context-free. But this contradicts our assumption.
In case you do not see why $(K-F)$, the difference of a context-free and a finite language must again be context-free: take a PDA accepting $K$. You can modify its control such that it additionally checks the input against the finite list of words in $F$ while it does the computation for $K$. If it accepts a word via the computation for $K$ but this word is on the list, the modified PDA rejects.
-
$\begingroup$ Thanks for the explained answer, I want to ask about your intuition of how you got to $L=(K-F)\cup (L\cap F)$ to start reaching a contradiction, I would love to hear how you approached the question in order to reach this then prove it. (More like what behind the scenes thoughts you had before starting the proof?), Thanks alot! $\endgroup$– PwaolJun 1, 2022 at 20:34
-
1$\begingroup$ Well, $L=(K-F) \cup (L\cap F)$ is pure set theory. It results from trying to get an equation $L=\dots$ from our starting point $K=L\cup F$. Maybe draw the Venn diagram, if you do not see immediately how to get from one to the other (and be sure to have the part $L\cap F$ visible/not empty). Then we can look at the different parts of the union and try to see, whether they are context-free, which leads to the context-freeness of $L$. $\endgroup$ Jun 2, 2022 at 6:39
The key idea is that you can still take apply the Pumping Lemma for CFLs to $\{ a^{n}b^{n}c^{n} : n \geq 0\}$ to get some word outside of $L = \{ a^{n}b^{n}c^{n} : n \geq 0 \} \cup \{a,b\}$.
Note that if $L$ is not a CFL and we add infinitely many words, we may obtain a CFL (and in fact, a regular language). Let $\Sigma$ be our alphabet. As an example, $L \cup (\Sigma^{*} \setminus L) = \Sigma^{*}$, which is regular.
So the assumption about adding a finite number of words to remain a non-CFL is critical here.
