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}$

  • 1
    $\begingroup$ 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 :) $\endgroup$ – Shaull Jan 5 '20 at 10:21
  • $\begingroup$ @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. $\endgroup$ – Bram Vanbilsen Jan 5 '20 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).

  • $\begingroup$ 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. $\endgroup$ – Bram Vanbilsen Jan 5 '20 at 11:51
  • 1
    $\begingroup$ Consider a context-free language $L$, whose complement is not context free. What is the complement of the complement? $\endgroup$ – Shaull Jan 5 '20 at 12:21
  • $\begingroup$ Wow, makes a whole lot of sense... Thanks for the help! $\endgroup$ – Bram Vanbilsen Jan 5 '20 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.