8
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Union has trivial counterexamples because there are undecidable languages. Any such language with its complement works. $\endgroup$ – Raphael Feb 23 '12 at 17:56
  • $\begingroup$ My students are not yet familiar with the concept of undecidability. $\endgroup$ – Shir Feb 23 '12 at 18:01
  • 1
    $\begingroup$ You don’t need undecidable, you only need that neither the language nor its complement is a CFL. $\endgroup$ – Emil Jeřábek Feb 23 '12 at 18:03
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 23 '12 at 18:03
  • 2
    $\begingroup$ 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^*\}$. $\endgroup$ – Kaveh Feb 23 '12 at 18:06
11
$\begingroup$

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 $

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I like this answer. $\endgroup$ – Suresh Venkat Feb 23 '12 at 18:33

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.