<p>There are probably few or no "interesting" and "natural" closure properties for the class of languages that are <em>not</em> context-free. In fact that's probably true of: </p>

<ul>
<li><p>any class of languages that is defined by a specific automaton, grammar or computational model -- the regular languages, the cfl's, various subclasses of the cfls such as the linear languages and the deterministic cfl's, the context-sensitive languages, bounded languages, and so on.</p></li>
<li><p>classes actually <em>defined</em> by closure properties, like the least family containing, say, {$a^n b^n$} and closed under the regular operations and transduction. In fact, AFL theory was all about things like that.</p></li>
</ul>

<p>The reason is that many if not most or all "interesting" closure properties have the ability to drastically simplify a language, for example map it down to finite sets or something equally simple. For example, you can always apply a constant homomorphism (h(a) = 0) to a non-context-free language and get the language of all strings of zeros, which is context-free (in fact regular). So if the very definition of the class entails that it is not very "simple" (like non-context-free), then closure takes you down to "simple" languages, that is, outside the class.</p>

<p>This might actually make an interesting research project, part of which, I would hazard a guess, would be to define "simple", "interesting" and "natural" in some suitable way, and also to find formal ways to deal with trivial and degenerate cases like the one I gave.</p>

<p>The union and concatenation operations would be one test of such a theory.  I'll conjecture that there are two non-cfl's which concatenate to $ \Sigma^*$ and others which union to that. I'd start with non-cfl's over a single letter, so you are really talking number theory and linear algebra.</p>

<hr>

<p>Adendum -- here are two languages that definitely concatenate to $a^*$ and are almost certainly not context-free:</p>

<p>$\{a^{n-i}:i = \lfloor \sqrt n \rfloor\}$</p>

<p>$\{a^{n+i}:i = \lfloor \sqrt n \rfloor\}$</p>

<p>If for some reason, those turn out CF, use an even stranger function than $ \sqrt x $</p>

CC BY-SA 3.0
2012-02-23T18:33:25.210Z
I like this answer.
Suresh Venkat
CC BY-SA 3.0
2012-02-23T18:28:28.960Z
2012-02-24T01:48:59.473Z
2012-02-24T01:48:59.473Z
David Lewis
<p>I was asked the following by a student, and couldn't come up with a complete answer:</p>

<p>Are there any closure properties for the class of languages that are <em>not</em> context free?</p>

<p>It's fairly easy to find examples that show that it is not closed under intersection and iteration (Kleene star operator), but how about union and concatenation? My guess is that it's not closed under either, so unless I'm way off, what I'm looking for are examples for two non-CFLs that their union or concatenation is a CFL.</p>

CC BY-SA 3.0
2012-02-23T17:56:54.590Z
Union has trivial counterexamples because there are undecidable languages. Any such language with its complement works.
Raphael
CC BY-SA 3.0
2012-02-23T18:01:46.577Z
My students are not yet familiar with the concept of undecidability.
Shir
CC BY-SA 3.0
2012-02-23T18:03:15.627Z
You don’t need undecidable, you only need that neither the language nor its complement is a CFL.
Emil Jeřábek
CC BY-SA 3.0
2012-02-23T18:03:37.400Z
Concatenation has also trivial counterexamples: take any two non-context-free languages L1 and L2 whose union is Σ*, and add the empty string to both L1 and L2.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-23T18:04:39.570Z
@TsuyoshiIto, would you mind specifying what you mean?
Shir
CC BY-SA 3.0
2012-02-23T18:05:46.133Z
@Shir: Sorry, my comment was originally incorrect.  I corrected it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-23T18:06:26.357Z
Intersection is easy, take two disjoint languages from $\bar{CFL}$, e.g. $\{0w : w \in L_1\}$ and $\{1w : w \in L_1\}$. Union is similarly easy, take two languages whose union is $\Sigma^*$, $\{0w : w \in L_1\} \cup \{1w : w \in \Sigma^*\}$ and $\{1w : w \in L_1\} \cup \{0w : w \in \Sigma^*\}$.
Kaveh
CC BY-SA 3.0
2012-02-23T18:08:47.300Z
Hi guys, you're all going around the same point, so if one of you could actually specify a non-CFL whose complement is non-CFL, that would be great.
Shir
CC BY-SA 3.0
2012-02-23T18:11:08.373Z
No, this question is off topic on cstheory.stackexchange.com, a website for research-level questions.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-23T18:15:23.803Z
Shir, use any language $L_1$ in $\bar{CFL}$ that you have proven to be so in your course. Raphael has already provided one but you didn't like it, and we cannot guess what you like or have covered in your course.
Kaveh
CC BY-SA 3.0
2012-02-23T18:41:43.833Z
@Kaveh In your comments, $L_1 \in \bar{CFL}$? Great (because simple) observations, by the way.
Raphael
CC BY-SA 3.0
2012-02-23T23:40:17.173Z
@Raphael, yes, I should have stated it in the first one.
Kaveh
CC BY-SA 3.0
2012-02-25T12:17:28.740Z
Note also [this answer](http://cstheory.stackexchange.com/a/9100/1546) to a related question.
Raphael
<fl.formal-languages><context-free-languages>
Non-CFL closure properties
Shir
# Non-CFL closure properties

(Asked by: username_0 on 2012-02-23)

I was asked the following by a student, and couldn't come up with a complete answer:

Are there any closure properties for the class of languages that are *not* context free?

It's fairly easy to find examples that show that it is not closed under intersection and iteration (Kleene star operator), but how about union and concatenation? My guess is that it's not closed under either, so unless I'm way off, what I'm looking for are examples for two non-CFLs that their union or concatenation is a CFL.

**Tags:** fl.formal-languages, context-free-languages
> **Comments:**
> **username_1**: Union has trivial counterexamples because there are undecidable languages. Any such language with its complement works.  
> **username_0**: My students are not yet familiar with the concept of undecidability.  
> **username_2**: You don’t need undecidable, you only need that neither the language nor its complement is a CFL.  
> **username_3**: Concatenation has also trivial counterexamples: take any two non-context-free languages L1 and L2 whose union is Σ*, and add the empty string to both L1 and L2.  
> **username_0**: @TsuyoshiIto, would you mind specifying what you mean?  
> **username_3**: @Shir: Sorry, my comment was originally incorrect.  I corrected it.  
> **username_4**: Intersection is easy, take two disjoint languages from $\bar{CFL}$, e.g. $\{0w : w \in L_1\}$ and $\{1w : w \in L_1\}$. Union is similarly easy, take two languages whose union is $\Sigma^*$, $\{0w : w \in L_1\} \cup \{1w : w \in \Sigma^*\}$ and $\{1w : w \in L_1\} \cup \{0w : w \in \Sigma^*\}$.  
> **username_0**: Hi guys, you're all going around the same point, so if one of you could actually specify a non-CFL whose complement is non-CFL, that would be great.  
> **username_3**: No, this question is off topic on cstheory.stackexchange.com, a website for research-level questions.  
> **username_4**: Shir, use any language $L_1$ in $\bar{CFL}$ that you have proven to be so in your course. Raphael has already provided one but you didn't like it, and we cannot guess what you like or have covered in your course.  
> **username_1**: @Kaveh In your comments, $L_1 \in \bar{CFL}$? Great (because simple) observations, by the way.  
> **username_4**: @Raphael, yes, I should have stated it in the first one.  
> **username_1**: Note also [this answer](http://cstheory.stackexchange.com/a/9100/1546) to a related question.  

---

## 1 answers

### Answer by username_5 on 2012-02-23. Score: 11 | Accepted answer

There are probably few or no "interesting" and "natural" closure properties for the class of languages that are *not* context-free. In fact that's probably true of:

* any class of languages that is defined by a specific automaton, grammar or computational model -- the regular languages, the cfl's, various subclasses of the cfls such as the linear languages and the deterministic cfl's, the context-sensitive languages, bounded languages, and so on.
* classes actually *defined* by closure properties, like the least family containing, say, {$a^n b^n$} and closed under the regular operations and transduction. In fact, AFL theory was all about things like that.

The reason is that many if not most or all "interesting" closure properties have the ability to drastically simplify a language, for example map it down to finite sets or something equally simple. For example, you can always apply a constant homomorphism (h(a) = 0) to a non-context-free language and get the language of all strings of zeros, which is context-free (in fact regular). So if the very definition of the class entails that it is not very "simple" (like non-context-free), then closure takes you down to "simple" languages, that is, outside the class.

This might actually make an interesting research project, part of which, I would hazard a guess, would be to define "simple", "interesting" and "natural" in some suitable way, and also to find formal ways to deal with trivial and degenerate cases like the one I gave.

The union and concatenation operations would be one test of such a theory. I'll conjecture that there are two non-cfl's which concatenate to $ \Sigma^\*$ and others which union to that. I'd start with non-cfl's over a single letter, so you are really talking number theory and linear algebra.

---

Adendum -- here are two languages that definitely concatenate to $a^\*$ and are almost certainly not context-free:

$\{a^{n-i}:i = \lfloor \sqrt n \rfloor\}$

$\{a^{n+i}:i = \lfloor \sqrt n \rfloor\}$

If for some reason, those turn out CF, use an even stranger function than $ \sqrt x $

> **Comments:**
> **username_6**: I like this answer.  

---

