13
$\begingroup$

I am trying to separate classes of formal languages from each other. One of these classes is the class of context-free languages. To this end, it would be handy to have a list of languages which are not context-free, but still somehow easy to understand. I am particularly interested in languages over a binary alphabet $\{a, b\}$.

I can only list a few. (I can trivially alter these examples, but that's not the point.)

  • $\{a^n b^n c^n \mid n \in \mathbb{N}\}$
  • $\{a^n b^n a^n \mid n \in \mathbb{N}\}$ or $\{a^n b^n a^n b^n \mid n \in \mathbb{N}\}$
  • $\{ww \mid w \in \{a,b\}^*\}$

Conceptually, the first two examples are not context-free because we would have to "remember" the number $n$ and then check against $n$ twice (but we can only check once against $n$ before we "forget" $n$; think of a pushdown automaton). The third example is not context-free because while we can memorize all the letters of $w$, we can only check against them in reversed order (the language of all palindromes is context-free).

Are there further "nice" non-context-free languages?

Edit: I think this question is most helpful for others if I list the examples from the answers for quick accessibility. Further explanations can be found in the respective answers, which I shall also link.

  • $\{a^{n^2} \mid n \in \mathbb{N}\}$ (link to answer)

  • $\{a^{n} b^{n^2} \mid n \in \mathbb{N}\}$ (link to answer)

  • $\{a^n \mid n \text{ is a prime number}\}$ (link to answer)

  • $\{a^{2^n} \mid n \in \mathbb{N}\}$ (link to answer)

  • $\{w \in \{a,b,c\}^* : \left|{w}\right|_a = \left|{w}\right|_b = \left|{w}\right|_c\}$ (where $\left|{w}\right|_a$ denotes the number of occurences of the symbol $a$ inside $w$) (link to answer)

  • $\{xyyz \mid x, y, z \in \{a, b, c\}^*\}$ (link to answer)

  • $\{a^nb^ma^nb^m \mid n, m \in \mathbb{N}\}$ (link to answer)

  • $\{v \# w \mid v, w \in \{a, b\}^*, \left|v\right| = \left|w\right|, v \neq w\}$ (Found in another question. The separater $\#$ is crucial here.)

$\endgroup$
4
  • 6
    $\begingroup$ I think I disagree with the vote to close. This question isn't an undergrad HW question like "Give an example of a non-CFL". The OP gave several standard examples and is asking if there are other "nice" non-CFLs, even specifying what is meant by the always-ambiguous-but-sometimes-useful term "nice". Obv "most" languages aren't context-free, e.g. EXP-complete languages unconditionally. But those are nowhere near as easy to understand as the examples given in the OQ. $\endgroup$ Commented Mar 7 at 15:10
  • 2
    $\begingroup$ did you want examples that have relatively low complexity, like in P (or maybe in NP)? BTW, there is also an associated complexity class that is equal to a natural class of circuits LogCFL = SAC^1 (complexityzoo.net/Complexity_Zoo:L#logcfl). Since LogCFL contains NL, all your examples are actually in LogCFL (so in that sense they are "not too far from context-free", even though in a formal language / Chomsky-like sense of course they aren't CFLs). $\endgroup$ Commented Mar 7 at 15:14
  • $\begingroup$ I have added many examples from the answers because (in my opinion) this will make this post more useful for others. Please inform me (or, if you have a very strong opinion on this, edit my question) if this violates the etiquettes on this site. $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 10:45
  • 1
    $\begingroup$ @JoshuaGrochow Your follow-up question aims directly at the term "nice". The kinds of examples I am looking for should be "quickly described". I would say that the examples we have seen so far can all be written down in a fairly short manner, and we understand easily what is meant. This is (I think ...) the criterion, instead of a certain (low) complexity. $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 11:14

4 Answers 4

11
$\begingroup$

If I had to summarize the capabilities/limitations of CF languages I would say:

  • they can pair "things" but two distinct pairings cannot overlap
  • they can "count" but only linearly (somewhat inherited from the regular languages)

Your $\{ a^n b^n a^n \}$ (or its more raw version $\{\{a,b,c\}^* \mid \#(a) = \#(b) = \#(c) \}$) "breaks" the pairing capabilities.

This one:

$L_{count} = \{ a^{n^2} \}$ (or its pairing version $\{a^nb^{n^2}\}$)

"breaks" the "linear counting" capabilities of CFL.

Addendum:

  • Context-free languages can also "divide" ...

$L = \{ w \in \{a,b\}^* \mid \forall 1 < k < k_0 \quad \lnot \exists q \text{ s.t. } w = q^k \}$ ($k_0$ is fixed)

is CF.

But it is an open problem if the set of primitive words is CF:

$L_{primitive} = \{ w \in \{a,b\}^* \mid \forall 1 < k \quad \lnot \exists q \text{ s.t. } w = q^k \}$

... so $L_{primitive}$ sits quietly on your separation line :-)

$\endgroup$
3
  • $\begingroup$ Thanks! I have added your examples to the list in my answer, hoping that you're fine with this. $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 11:05
  • $\begingroup$ Ok! Be aware that the first language of my Addendum IS context free. The second language is UNKNOWN (I added it only to show that there's still something on "the boundary" and we don't know on which side it should be placed). $\endgroup$ Commented Mar 8 at 11:09
  • $\begingroup$ Another classic example of overlapping pairings is given by the "cross-referencing" language $\{\, w\$w \mid w\in\Sigma^*\}\,$, where $\$$ is a marker symbol. (Of course, the analogous language without the marker symbol in the middle is even less context-free, lol). See the following answer for historical context: math.stackexchange.com/a/460400 $\endgroup$ Commented Mar 9 at 16:12
6
$\begingroup$

Two simple examples of non-context-free languages are PRIMES $= \{ a^p \mid p \text{ prime} \}$ and POWERS $= \{ a^{2^n} \mid n\ge 0 \}$. One can prove that they are not context-free by the pumping lemma.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! I have added your examples to the list in my answer, hoping that you're fine with this. $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 11:05
3
$\begingroup$

You can group non-context-free languages into groups depending on what lemma you use to show that they are not context-free.
Noam already mentioned the pumping lemma in his answer, let me mention the less-known Interchange Lemma.
You can use this to show that the language of repetitive strings (i.e., strings of the form $xyyz$ with $|y|>0$) over an alphabet of three or more characters is not context-free (quoting (myself) from Wikipedia).
There are also more complicated forms of the pumping lemma that you can use, see Strong iteration lemmata for regular, linear, context-free, and linear indexed languages, or my own amazing lemma combining these two lemmas.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. I have tried to understand the Wikipedia article on the Interchange Lemma. It says there that "each of $\left| w_i \right|, \left| x_i \right|, \left| y_i \right|$ is independent of $i$". Does this mean that $\left| w_i \right| = \left| w_j \right|$ for any choice of $i$ and $j$, and likewise for $w$ replaced by $x$ or $y$? $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 11:00
  • $\begingroup$ Also, do you know how to prove this lemma? I have no idea where to start. Can you offer a hint? $\endgroup$
    – NerdOnTour
    Commented Mar 8 at 11:01
  • 1
    $\begingroup$ This website is for research levels questions, these would be more appropriate to ask on cs.stackexchange.com. $\endgroup$
    – domotorp
    Commented Mar 8 at 15:00
1
$\begingroup$

The following is kind of a variant of the examples already given, but I believe it is sufficiently different that is worth mentioning.

$L=\{a^n b^m a^n b^m\mid n,m\in \mathbb{N}\}$

Proof by using the Pumping Lemma.

$\endgroup$

Your Answer

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

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