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.
Best Answer
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.