# Closure properties of non-context-free languages (concatenation & complement)

I am trying to proof the properties of the complement and concatenation of two non-context-free languages $$L_1$$ and $$L_2$$.
I believe that both of these languages are closed under complement and concatenation but can't seem to find a solid proof for it. I'm leaning towards them being closed because I can't find any counter examples.
I already proved that non-context-free languages are not closed under union and intersection, so I can use those properties (if applicable).

So in short what I want to proof, given $$L_1, L_2$$ are non-context-free languages:
$$L_1L_2 \in S_{nonContextFree}$$
$$\overline{L_1} \in S_{nonContextFree}$$

• Languages cannot be closed/not closed under complementation, what you're referring to are classes of languages. As for your question, a small hint: if you find it hard to prove the claim, perhaps try to find a counterexample :) Commented Jan 5, 2020 at 10:21
• @Shaull whoops, something go lost in translation there! Thanks for the counterexample tip, but as mentioned in my question, I couldn't find any. Therefor my suspicion that the. classes of non-context-free languages are closed under these operations. Commented Jan 5, 2020 at 10:29

As for closure under complementation -- consider the following hint: context-free languages are not closed under complementation.

Regarding concatenation, this is slightly more tricky, but non-context free languages are not closed under complementation.

There are many ways of finding counterexamples for the latter, one is the following "trick":

Let $$L$$ be some non-context free language over some alphabet $$\Sigma$$, that does not contain $$0,1$$. Now define two languages: $$A=(1\cdot \Sigma^*)\cup (0\cdot L)\cup \{\epsilon\}$$ and $$B=(0\cdot \Sigma^*)\cup (1\cdot L)\cup \{\epsilon\}$$

It is not hard to prove that neither $$A$$ nor $$B$$ are context free, basically due to presence of $$L$$.

However, we have that $$A\cdot B=\{0,1\}\cdot \Sigma^*\cup \{\epsilon\}$$, which is regular (and in particular context-free).

• For complementation, does that automatically mean that it is also not closed under non-context free languages? I do not directly see how you would derive one from the other. as they are completely disjunct. Commented Jan 5, 2020 at 11:51
• Consider a context-free language $L$, whose complement is not context free. What is the complement of the complement? Commented Jan 5, 2020 at 12:21
• Wow, makes a whole lot of sense... Thanks for the help! Commented Jan 5, 2020 at 12:31