98
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Ntpick: it is undecidable to show whether a language is context-free. $\endgroup$ May 26, 2017 at 8:33
  • 1
    $\begingroup$ @reinierpost I don't see how your comment relates to the question. It's about proving things, not deciding (algorithmically). $\endgroup$
    – Raphael
    May 28, 2017 at 16:43
  • $\begingroup$ 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. $\endgroup$ May 29, 2017 at 10:20
  • $\begingroup$ @reinierpost That line of reasoning seems to assume that undecidable implies (equals?) hard to prove. I wonder if that's true. $\endgroup$
    – Raphael
    May 29, 2017 at 11:32

5 Answers 5

73
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ indeed, kozen's game is the way to go about this. $\endgroup$
    – socrates
    Dec 2, 2016 at 23:50
49
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Mar 18, 2012 at 10:32
  • 1
    $\begingroup$ That's fine, but note that the pumping lemma is a particular case of Ogden's lemma ;-) $\endgroup$
    – Janoma
    Mar 18, 2012 at 13:40
  • $\begingroup$ Of course. Still, most people will try PL first; many don't even know OL. $\endgroup$
    – Raphael
    Mar 18, 2012 at 13:42
  • 1
    $\begingroup$ 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 $\endgroup$
    – sdcvvc
    Jun 15, 2013 at 23:19
  • $\begingroup$ 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. $\endgroup$
    – wvxvw
    Jan 23, 2016 at 12:35
36
$\begingroup$

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)
$\endgroup$
1
19
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Mar 13, 2012 at 2:22
  • $\begingroup$ I am not looking for a computable method but for pen & paper proof techniques. The latter does not necessarily imply the former. $\endgroup$
    – Raphael
    Mar 13, 2012 at 6:46
13
$\begingroup$

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

Bader-Moura’s condition (BMC)

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.

Reference: Bader, C., Moura, A., A Generalization of Ogden’s Lemma. JACM 29, no. 2, (1982), 404–407

$\endgroup$
4
  • 2
    $\begingroup$ 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 ... $\endgroup$ Jul 3, 2013 at 9:25
  • $\begingroup$ @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). $\endgroup$
    – Vor
    Jul 3, 2013 at 10:28
  • $\begingroup$ you are welcome to post it, don't have time right now. $\endgroup$ Jul 3, 2013 at 11:02
  • $\begingroup$ This answer would profit from an example. $\endgroup$
    – Raphael
    May 25, 2015 at 16:49

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.