<p>If I had to summarize the capabilities/limitations of CF languages I would say:</p>
<ul>
<li>they can pair &quot;things&quot; but two distinct pairings cannot overlap</li>
<li>they can &quot;count&quot; but only linearly (somewhat inherited from the regular languages)</li>
</ul>
<p>Your <span class="math-container">$\{ a^n b^n a^n \}$</span> (or its more raw version <span class="math-container">$\{\{a,b,c\}^* \mid \#(a) = \#(b) = \#(c) \}$</span>) &quot;breaks&quot; the pairing capabilities.</p>
<p>This one:</p>
<p><span class="math-container">$L_{count} = \{ a^{n^2}  \}$</span>    (or its pairing version <span class="math-container">$\{a^nb^{n^2}\}$</span>)</p>
<p>&quot;breaks&quot; the &quot;linear counting&quot; capabilities of CFL.</p>
<p><strong>Addendum</strong>:</p>
<ul>
<li>Context-free languages can also &quot;divide&quot; ...</li>
</ul>
<p><span class="math-container">$L = \{ w \in \{a,b\}^* \mid \forall 1 &lt; k &lt; k_0 \quad \lnot \exists q \text{ s.t. } w = q^k \}$</span> (<span class="math-container">$k_0$</span> is fixed)</p>
<p>is CF.</p>
<p>But it is an <strong>open problem</strong> if the set of primitive words is CF:</p>
<p><span class="math-container">$L_{primitive} = \{ w \in \{a,b\}^* \mid \forall 1 &lt; k \quad \lnot \exists q \text{ s.t. } w = q^k \}$</span></p>
<p>... so <span class="math-container">$L_{primitive}$</span> sits quietly on your separation line :-)</p>

CC BY-SA 4.0
2024-03-08T11:05:03.213Z
Thanks! I have added your examples to the list in my answer, hoping that you're fine with this.
NerdOnTour
CC BY-SA 4.0
2024-03-08T11:09:15.930Z
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).
Marzio De Biasi
CC BY-SA 4.0
2024-03-09T16:12:04.283Z
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: https://math.stackexchange.com/a/460400
Hermann Gruber
CC BY-SA 4.0
2024-03-08T08:40:07.100Z
2024-03-18T11:13:27.337Z
2024-03-18T11:13:27.337Z
Marzio De Biasi
<p>Two simple examples of non-context-free languages are PRIMES <span class="math-container">$= \{ a^p \mid p \text{ prime} \}$</span> and POWERS <span class="math-container">$= \{ a^{2^n} \mid n\ge 0 \}$</span>. One can prove that they are not context-free by the <a href="https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages" rel="noreferrer">pumping lemma</a>.</p>

CC BY-SA 4.0
2024-03-08T11:05:15.627Z
Thanks! I have added your examples to the list in my answer, hoping that you're fine with this.
NerdOnTour
CC BY-SA 4.0
2024-03-08T05:42:34.957Z
2024-03-08T05:42:34.957Z
Noam Zeilberger
<p>You can group non-context-free languages into groups depending on what lemma you use to show that they are not context-free.<br />
Noam already mentioned the pumping lemma in his answer, let me mention the less-known <a href="https://en.wikipedia.org/wiki/Interchange_lemma" rel="nofollow noreferrer">Interchange Lemma</a>.<br />
You can use this to show that the language of repetitive strings (i.e., strings of the form <span class="math-container">$xyyz$</span> with <span class="math-container">$|y|&gt;0$</span>) over an alphabet of three or more characters is not context-free (quoting (myself) from Wikipedia).<br />
There are also more complicated forms of the pumping lemma that you can use, see <a href="https://doi.org/10.1007/3-540-48321-7_18" rel="nofollow noreferrer">Strong iteration lemmata for regular, linear, context-free, and
linear indexed languages</a>, or <a href="https://arxiv.org/abs/1901.03913" rel="nofollow noreferrer">my own amazing lemma</a> combining these two lemmas.</p>

CC BY-SA 4.0
2024-03-08T11:00:55.897Z
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$?
NerdOnTour
CC BY-SA 4.0
2024-03-08T11:01:57.123Z
Also, do you know how to prove this lemma? I have no idea where to start. Can you offer a hint?
NerdOnTour
CC BY-SA 4.0
2024-03-08T15:00:29.363Z
This website is for research levels questions, these would be more appropriate to ask on https://cs.stackexchange.com/.
domotorp
CC BY-SA 4.0
2024-03-08T08:13:15.200Z
2024-03-08T08:13:15.200Z
domotorp
<p>The following is kind of a variant of the examples already given, but I believe it is sufficiently different that is worth mentioning.</p>
<p><span class="math-container">$L=\{a^n b^m a^n b^m\mid n,m\in \mathbb{N}\}$</span></p>
<p>Proof by using the Pumping Lemma.</p>

CC BY-SA 4.0
2024-03-14T16:35:26.997Z
2024-03-14T16:35:26.997Z
Pavlos M.
<p>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 <span class="math-container">$\{a, b\}$</span>.</p>
<p>I can only list a few. (I can trivially alter these examples, but that's not the point.)</p>
<ul>
<li><span class="math-container">$\{a^n b^n c^n \mid n \in \mathbb{N}\}$</span></li>
<li><span class="math-container">$\{a^n b^n a^n \mid n \in \mathbb{N}\}$</span> or <span class="math-container">$\{a^n b^n a^n b^n \mid n \in \mathbb{N}\}$</span></li>
<li><span class="math-container">$\{ww \mid w \in \{a,b\}^*\}$</span></li>
</ul>
<p>Conceptually, the first two examples are not context-free because we would have to &quot;remember&quot; the number <span class="math-container">$n$</span> and then check against <span class="math-container">$n$</span> twice (but we can only check once against <span class="math-container">$n$</span> before we &quot;forget&quot; <span class="math-container">$n$</span>; think of a pushdown automaton). The third example is not context-free because while we can memorize all the letters of <span class="math-container">$w$</span>, we can only check against them in reversed order (the language of all palindromes is context-free).</p>
<p>Are there further &quot;nice&quot; non-context-free languages?</p>
<p><strong>Edit:</strong>
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.</p>
<ul>
<li><p><span class="math-container">$\{a^{n^2} \mid n \in \mathbb{N}\}$</span> (<a href="https://cstheory.stackexchange.com/a/54033/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{a^{n} b^{n^2} \mid n \in \mathbb{N}\}$</span> (<a href="https://cstheory.stackexchange.com/a/54033/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{a^n \mid n \text{ is a prime number}\}$</span> (<a href="https://cstheory.stackexchange.com/a/54031/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{a^{2^n} \mid n \in \mathbb{N}\}$</span> (<a href="https://cstheory.stackexchange.com/a/54031/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{w \in \{a,b,c\}^* : \left|{w}\right|_a = \left|{w}\right|_b = \left|{w}\right|_c\}$</span> (where <span class="math-container">$\left|{w}\right|_a$</span> denotes the number of occurences of the symbol <span class="math-container">$a$</span> inside <span class="math-container">$w$</span>) (<a href="https://cstheory.stackexchange.com/a/54033/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{xyyz \mid x, y, z \in \{a, b, c\}^*\}$</span> (<a href="https://cstheory.stackexchange.com/a/54032/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{a^nb^ma^nb^m \mid n, m \in \mathbb{N}\}$</span> (<a href="https://cstheory.stackexchange.com/a/54053/72192">link to answer</a>)</p>
</li>
<li><p><span class="math-container">$\{v \# w \mid v, w \in \{a, b\}^*, \left|v\right| = \left|w\right|, v \neq w\}$</span> (Found in <a href="https://cs.stackexchange.com/q/74701/144862">another question</a>. The separator <span class="math-container">$\#$</span> is crucial here.)</p>
</li>
</ul>

CC BY-SA 4.0
2024-03-07T15:10:47.593Z
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.
Joshua Grochow
CC BY-SA 4.0
2024-03-07T15:14:31.287Z
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 (https://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).
Joshua Grochow
CC BY-SA 4.0
2024-03-08T10:45:57.903Z
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.
NerdOnTour
CC BY-SA 4.0
2024-03-08T11:14:30.137Z
@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.
NerdOnTour
<fl.formal-languages><context-free><examples>
List of nice non-context-free languages
NerdOnTour
# List of nice non-context-free languages

(Asked by: username_0 on 2024-03-07)

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](https://cstheory.stackexchange.com/a/54033/72192))
* $\{a^{n} b^{n^2} \mid n \in \mathbb{N}\}$ ([link to answer](https://cstheory.stackexchange.com/a/54033/72192))
* $\{a^n \mid n \text{ is a prime number}\}$ ([link to answer](https://cstheory.stackexchange.com/a/54031/72192))
* $\{a^{2^n} \mid n \in \mathbb{N}\}$ ([link to answer](https://cstheory.stackexchange.com/a/54031/72192))
* $\{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](https://cstheory.stackexchange.com/a/54033/72192))
* $\{xyyz \mid x, y, z \in \{a, b, c\}^\*\}$ ([link to answer](https://cstheory.stackexchange.com/a/54032/72192))
* $\{a^nb^ma^nb^m \mid n, m \in \mathbb{N}\}$ ([link to answer](https://cstheory.stackexchange.com/a/54053/72192))
* $\{v \# w \mid v, w \in \{a, b\}^\*, \left|v\right| = \left|w\right|, v \neq w\}$ (Found in [another question](https://cs.stackexchange.com/q/74701/144862). The separator $\#$ is crucial here.)

**Tags:** fl.formal-languages, context-free, examples
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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 (https://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).  
> **username_0**: 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.  
> **username_0**: @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.  

---

## 4 answers

### Answer by username_2 on 2024-03-08. Score: 11

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

> **Comments:**
> **username_0**: Thanks! I have added your examples to the list in my answer, hoping that you're fine with this.  
> **username_2**: 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).  
> **username_3**: 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: https://math.stackexchange.com/a/460400  

---

### Answer by username_4 on 2024-03-08. Score: 6

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](https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages).

> **Comments:**
> **username_0**: Thanks! I have added your examples to the list in my answer, hoping that you're fine with this.  

---

### Answer by username_5 on 2024-03-08. Score: 3

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](https://en.wikipedia.org/wiki/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](https://doi.org/10.1007/3-540-48321-7_18), or [my own amazing lemma](https://arxiv.org/abs/1901.03913) combining these two lemmas.

> **Comments:**
> **username_0**: 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$?  
> **username_0**: Also, do you know how to prove this lemma? I have no idea where to start. Can you offer a hint?  
> **username_5**: This website is for research levels questions, these would be more appropriate to ask on https://cs.stackexchange.com/.  

---

### Answer by username_6 on 2024-03-14. Score: 1

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.


---

