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
- $z_i = w_ix_iy_i$ for $i=1,\dots,k$,
- $|w_1| = |w_2| = \dots = |w_k|$,
- $|y_1| = |y_2| = \dots = |y_k|$,
- $m \geq |x_1| = |x_2| = \dots = |x_k| > \frac{m}{2}$ and
- $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.
- An “Interchange Lemma” for Context-Free Languages by W. Ogden, R. J. Ross and K. Winklmann (1985)
- Swapping Lemmas for Regular and Context-Free Languages by T. Yamakami (2008)
- The interchange or pump (DI)lemmas for context-free languages by R. Boonyavatana and G. Slutzki (1988)