# How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all grammars (or automata) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

• Ntpick: it is undecidable to show whether a language is context-free. – reinierpost May 26 '17 at 8:33
• @reinierpost I don't see how your comment relates to the question. It's about proving things, not deciding (algorithmically). – Raphael May 28 '17 at 16:43
• Just making the point that it's not easy to show that a language is context-free, in general. If it's easy for frafl, that must be owing to certain special conditions that don't hold for languages in general, such as being given a pushdown automaton that describes the language. – reinierpost May 29 '17 at 10:20
• @reinierpost That line of reasoning seems to assume that undecidable implies (equals?) hard to prove. I wonder if that's true. – Raphael May 29 '17 at 11:32

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.

That said, I am also interested in other techniques than the pumping lemma if there are any.

EDIT: Here is an example for the pumping lemma: suppose the language $L=\{ a^k \mid k ∈ P\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

1. The pumping lemma gives you a $p$
2. You give a word $s$ of the language of length at least $p$
3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
4. You give an integer $n≥0$
5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is a prime number) will do the trick. Then the pumping lemma gives you $uvxyz$ with $|vy|≥1$. Do disprove the context-freeness, you need to find $n$ such that $|uv^nxy^nz|$ is not a prime number.

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

A second example is the language $\{ww \mid w \in \{a,b\}^{\ast}\}$. We (of course) have to choose a string and show that there's no possible way it can be broken into those five parts and have every derived pumped string remain in the language.

The string $s=a^{p}b^{p}a^{p}b^{p}$ is a suitable choice for this proof. Now we just have to look at where $v$ and $y$ can be. The key parts are that $v$ or $y$ has to have something in it (perhaps both), and that both $v$ and $y$ (and $x$) are contained in a length $p$ substring - so they can't be too far apart.

This string has a number of possibilities for where $v$ and $y$ might be, but it turns out that several of the cases actually look pretty similar.

1. $vy \in a^{\ast}$ or $vy \in b^{\ast}$. So then they're both contained in one of the sections of continguous $a$s or $b$s. This is the relatively easy case to argue, as it kind of doesn't matter which they're in. Assume that $|vy| = k \leq p$.
• If they're in the first section of $a$s, then when we pump, the first half of the new string is $a^{p+k}b^{p-k/2}$, and the second is $b^{k/2}a^{p}b^{p}$. Obviously this is not of the form $ww$.
• The argument for any of the three other sections runs pretty much the same, it's just where the $k$ and $k/2$ ends up in the indices.
2. $vxy$ straddles two of the sections. In this case pumping down is your friend. Again there's several places where this can happen (3 to be exact), but I'll just do one illustrative one, and the rest should be easy to figure out from there.
• Assume that $vxy$ straddles the border between the first $a$ section and the first $b$ section. Let $vy = a^{k_{1}}b^{k_{2}}$ (it doesn't matter precisely where the $a$s and $b$s are in $v$ and $y$, but we know that they're in order). Then when we pump down (i.e. the $i=0$ case), we get the new string $s'=a^{p-k_{1}}b^{p-k_{2}}a^{p}b^{p}$, but then if $s'$ could be split into $ww$, the midpoint must be somewhere in the second $a$ section, so the first half is $a^{p-k_{1}}b^{p-k_{2}}a^{(k_{1}+k_{2})/2}$, and the second half is $a^{p-(k_{1}+k_{2})/2}b^{p}$. Clearly these are not the same string, so we can't put $v$ and $y$ there.

The remaining cases should be fairly transparent from there - they're the same ideas, just putting $v$ and $y$ in the other 3 spots in the first instance, and 2 spots in the second instance. In all cases though, you can pump it in such a way that the ordering is clearly messed up when you split the string in half.

• indeed, kozen's game is the way to go about this. – socrates Dec 2 '16 at 23:50

## Ogden's Lemma

Lemma (Ogden). Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of marking $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that

1. $vx$ has at least one distinguished position.
2. $vwx$ has at most $N$ distinguished positions.
3. For all $i\geq 0$, $uv^iwx^iy\in L$.

Example. Let $L=\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$. Assume $L$ is context-free, and let $N$ be the constant given by Ogden's lemma. Let $z=a^Nb^{N+N!}c^{N+2N!}$ (which belongs to $L$), and suppose we mark as distinguished all the positions of the symbol $a$ (i.e. the first $N$ positions of $z$). Let $z=uvwxy$ be a decomposition of $z$ satisfying the conditions from Ogden's lemma.

• If $v$ or $x$ contain different symbols, then $uv^2wx^2y\notin L$, because there will be symbols in the wrong order.
• At least one of $v$ and $x$ must contain only symbols $a$, because only the $a$'s have been distinguished. Thus, if $x\in L(b^*)$ or $x\in L(c^*)$, then $v\in L(A^+)$. Let $p=|v|$. Then $1\leq p\leq N$, which means $p$ divides $N!$. Let $q=N!/p$. Then $z'=uv^{2q+1}wx^{2q+1}y$ should belong to $L$. However, $v^{2q+1}=a^{2pq+p}=a^{2N!+p}$. Since $uwy$ has exactly $N-p$ symbols $a$, then $z'$ has $2N!+N$ symbols $a$. But both $v$ and $x$ don't have $c$'s, so $z'$ also has $2N!+N$ symbols $c$, which means $z'\notin L$, and this contradicts Ogden's lemma. A similar contradiction occurs if $x\in L(A^+)$ or $x\in L(c^*)$. We conclude $L$ is not context-free.

Exercise. Using Ogden's Lemma, show that $L=\{a^ib^jc^kd^{\ell}:i=0\text{ or }j=k=\ell\}$ is not context-free.

## Pumping Lemma

This is a particular case of Ogden's Lemma in which all positions are distinguished.

Lemma. Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$, $z$ can be written as $z=uvwxy$, such that

1. $|vx|>0$.
2. $|vwx|\leq N$.
3. For all $i\geq 0$, $uv^iwx^iy\in L$.

## Parikh's Theorem

This is even more technical than Ogden's Lemma.

Definition. Let $\Sigma=\{a_1,\ldots,a_n\}$. We define $\Psi_{\Sigma}:\Sigma^*\to\mathbb{N}^n$ by $$\Psi_{\Sigma}(w)=(m_1,\ldots,m_n),$$ where $m_i$ is the number of appearances of $a_i$ in $w$.

Definition. A subset $S$ of $\mathbb{N}^n$ is called linear if it can be written: $$S = \{\mathbf{u_0} + \sum_{1 \le i \le k} a_i \mathbf{u_i} : \text{ for some set of \mathbf{u_i} \in \mathbb{N}^n and a_i \in \mathbb{N}}\}$$

Definition. A subset $S$ of $\mathbb{N}^n$ is called semi-linear if it is the union of a finite collection of linear sets.

Theorem (Parikh). Let $L$ be a language over $\Sigma$. If $L$ is context-free, then $$\Psi_{\Sigma}[L]=\{\Psi_{\Sigma}(w):w\in L\}$$ is semi-linear.

Exercise. Using Parikh's Theorem, show that $L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$ is not context-free.

Exercise. Using Parikh's Theorem, show that any context-free language over a unary alphabet is also regular.

• I accepted jmad's answer because the question explicitly mentions Pumping Lemma. I appreciate your answer a lot, though; having all major methods collected here is a great thing. – Raphael Mar 18 '12 at 10:32
• That's fine, but note that the pumping lemma is a particular case of Ogden's lemma ;-) – Janoma Mar 18 '12 at 13:40
• Of course. Still, most people will try PL first; many don't even know OL. – Raphael Mar 18 '12 at 13:42
• A theorem by Ginsburg and Spanier, building on Parikh's theorem, gives a neccessary and sufficient condition for context-freeness in the bounded case. math.stackexchange.com/a/122472 – sdcvvc Jun 15 '13 at 23:19
• Can you please define "distinguished positions" in terms of other operations? Or at least informally? I find the definition of OL copied verbatim in many different places, but none of them so far cared to explain what that means. – wvxvw Jan 23 '16 at 12:35

### Closure Properties

Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this:

Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$.

This is often shorter (and often less error-prone) than using one of the other results that use less prior knowledge. It is also a general concept that can be applied all kinds of class of objects.

Example 1: Intersection with Regular Languages

We note $\mathcal L(e)$ the regular language specified by any regular expression $e$.

Let $L = \{w \mid w \in \{a,b,c\}^*, |w|_a = |w|_b = |w|_c\}$. As

$\qquad \displaystyle L \cap \mathcal{L}(a^*b^*c^*) = \{a^nb^nc^n \mid n \in \mathbb{N}\} \notin \mathrm{CFL}$

and $\mathrm{CFL}$ is closed under intersection with regular languages, $L \notin \mathrm{CFL}$.

Example 2: (Inverse) Homomorphism

Let $L = \{(ab)^{2n}c^md^{2n-m}(aba)^{n} \mid m,n \in \mathbb{N}\}$. With the homomorphism

$\qquad \displaystyle \phi(x) = \begin{cases} a &x=a \\ \varepsilon &x=b \\ b &x=c \lor x=d \end{cases}$

we have $\phi(L) = \{a^{2n}b^{2n}a^{2n} \mid n \in \mathbb{N}\}.$

Now, with

$\qquad \displaystyle \psi(x) = \begin{cases} aa &x=a \lor x=c \\ bb &x=b \end{cases}\quad\text{and}\quad L_1 = \{x^nb^ny^n \mid x,y \in \{a,c\}\wedge n \in \mathbb{N}\},$

we get $L_1 = \psi^{-1}(\phi(L)))$.

Finally, intersecting $L_1$ with the regular language $L_2 = \mathcal L(a^*b^*c^*)$ we get the language $L_3 = \{a^n b^n c^n \mid n \in \mathbb{N}\}$.

In total, we have $L_3 = L_2 \cap \psi^{-1}(\phi(L))$.

Now assume that $L$ was context-free. Then, since $\mathrm{CFL}$ is closed against homomorphism, inverse homomorphism, and intersection with regular sets, $L_3$ is context-free, too. But we know (via Pumping Lemma, if need be) that $L_3$ is not context-free, so this is a contradiction; we have shown that $L \notin \mathrm{CFL}$.

### Interchange Lemma

The Interchange Lemma [1] proposes a necessary condition for context-freeness that is even stronger than Ogden's Lemma. For example, it can be used to show that

$\qquad \{xyyz \mid x,y,z \in \{a,b,c\}^+\} \notin \mathrm{CFL}$

which resists many other methods. This is the lemma:

Let $L \in \mathrm{CFL}$. Then there is a constant $c_L$ such that for any integer $n\geq 2$, any set $Q_n \subseteq L_n = L \cap \Sigma^n$ and any integer $m$ with $n \geq m \geq 2$ there are $k \geq \frac{|Q_n|}{c_L n^2}$ strings $z_i \in Q_n$ with

1. $z_i = w_ix_iy_i$ for $i=1,\dots,k$,
2. $|w_1| = |w_2| = \dots = |w_k|$,
3. $|y_1| = |y_2| = \dots = |y_k|$,
4. $m \geq |x_1| = |x_2| = \dots = |x_k| > \frac{m}{2}$ and
5. $w_ix_jy_i \in L_n$ for all $(i,j) \in [1..k]^2$.

Applying it means to find $n,m$ and $Q_n$ such that 1.-4. hold but 5. is violated. The application example given in the original paper is very verbose and is therefore left out here.

At this time, I do not have a freely available reference and the formulation above is taken from a preprint of [1] from 1981. I appreciate help in tracking down better references. It appears that the same property has been (re)discovered recently [2].

### Other Necessary Conditions

Boonyavatana and Slutzki [3] survey several conditions similar to Pumping and Interchange Lemma.

1. An “Interchange Lemma” for Context-Free Languages by W. Ogden, R. J. Ross and K. Winklmann (1985)
2. Swapping Lemmas for Regular and Context-Free Languages by T. Yamakami (2008)
3. The interchange or pump (DI)lemmas for context-free languages by R. Boonyavatana and G. Slutzki (1988)

There is no general method since the set non-context-free-languages is not semi-decidable (a.k.a. r.e.). If there was a general method, we could use it to semi-decide this set.

The situation is even worse, since given two CFL's it is not possible to decide whether their intersection is also a CFL.

Reference: Hopcroft and Ullman, "Introduction to Automata Theory, Languages, and Computation", 1979.

• An interesting (but probably more advanced and open-ended question) would be categorizing the subclass of non-CFLs that can be proved to be non-CFL using a particular method. – Kaveh Mar 13 '12 at 2:22
• I am not looking for a computable method but for pen & paper proof techniques. The latter does not necessarily imply the former. – Raphael Mar 13 '12 at 6:46

A stronger version of the Ogden's condition (OC) is the

A language $$L\subseteq \Sigma^*$$ satisfies BMC if there exists a constant $$n$$ such that if $$z \in L$$ and we label in it "distinguished" positions $$d(z)$$ and $$e(z)$$ "excluded" positions, with $$d(z) > n^{e(z)+1}$$, then we may write $$z = uvwxy$$ such that:

1. $$d(vx) \geq 1$$ and $$e(vx) =0$$
2. $$d(vwx) \leq n^{e(vwx)+1}$$ and
3. for every $$i \geq 0$$, $$uv^iwx^iy$$ is in $$L$$.

We say that a language $$L \in BMC(\Sigma)$$ if $$L$$ satisfies the Bader-Moura’s condition.

We have $$CFL(\Sigma) \subset BMC(\Sigma) \subset OC(\Sigma)$$, so BMC is strictly stronger than OC.

• Why not just go all the way to Dömösi and Kudlek's generalisation dx.doi.org/10.1007/3-540-48321-7_18 ... – András Salamon Jul 3 '13 at 9:25
• @AndrásSalamon: I didn't know it! :-) ... perhaps you can post it as a new answer saying that OC, BMC, PC are special cases of it (all distinguished or no excluded positions). – Vor Jul 3 '13 at 10:28
• you are welcome to post it, don't have time right now. – András Salamon Jul 3 '13 at 11:02
• This answer would profit from an example. – Raphael May 25 '15 at 16:49