2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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, 2020 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, 2020 at 10:29

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • $\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, 2020 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, 2020 at 12:21
  • $\begingroup$ Wow, makes a whole lot of sense... Thanks for the help! $\endgroup$
    – Bram Vanbilsen
    Jan 5, 2020 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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