Proving that a Language is not Context-Free

Since context-free languages are so important, it is desirable to have some way of proving when a language isn't context-free. We did this for regular languages by choosing those which were ``big enough'' (ie. infinite) to cause a particular type of repetition (or periodicity) in their derivation. The nature of the ``pump'' (for regular expressions it was Kleene Closure) could then be used to characterise these languages.

So we consider some questions about context-free grammars:

• In what way does a CFG ``pump''?
  Repetition in a CFG is achieved by recursion in the rules. This can occur directly or indirectly, but will result in a derivation of the form: $A\; \rightarrow^*\; vAy$, where $A$ is a non-terminal, and $v$ and $y$ are strings.
• What is the effect of this ``pumping''?
  Each time we apply the sequence of rules which recurse back to $A$, we also generate an extra copy of both $v$ and $y$. Thus if we go through the sequence say $n$ times, we get the derivation $A\; \rightarrow^*\; v^nAy^n$
  

  This ``matching'' or ``balancing'' of two patterns is the hallmark of context-free languages.

• When does this ``pumping'' happen?
  This can be broken down into two sub-questions:
  • For what sort of parse tree does this ``pumping'' happen?
    If a derivation ``pumps'' on some non-terminal $A$, then this non-terminal must occur twice in some path from the root of the parse tree to one of the leaves. This is guaranteed to happen if we know that the grammar has, say, $m$ non-terminals altogether, and the parse tree for a string has a path with length greater than $m$ (we simply run out of non-terminals to label the nodes with, and so must repeat one!). So a parse tree contains a ``pump'' if its height is greater than $m$.
  • For what sort of strings does this ``pumping'' happen?
    Suppose the maximum number of symbols on the r.h.s. of any grammar rule of the language is $p$. Then each application of any rule generates at most $p$ symbols; (ie. each node of the parse tree has at most $p$ children). Thus a path of length $m$ or less can generate at most $p^m$ symbols. This means that if we have a string of length greater than $p^m$, there must have been a ``pump'' in the parse tree which generated it.
    
  Thus the ability to generate strings of length greater than $p^m$ indicates that the language represented by the grammar is infinite.
  

Let us suppose that u, x and z are strings such that:

$$\begin{array}{rcl} S & \rightarrow^* & uAz \\ & and & \\ A & \rightarrow^* & x \end{array}$$

and if, as assumed above, we have also that:

$$\begin{array}{rcl} A & \rightarrow^* & vAy \end{array}$$

The it should be clear that for any $i \geq 0$:

$$\begin{array}{ccccccccccc} S & \rightarrow^* & uAz & \rightar... ...\rightarrow^* uv^iAy^iz & \rightarrow^* & uv^ixy^iz \end{array}$$

Then we can generate the set $\{uxz, uvxyz, uv^2xy^2z, \ldots, uv^ixy^iz, \ldots\}$

Tying all this together we get: