Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

5 Answers

up vote 34 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
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
1  
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
1  
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
add comment

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 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: (Inverse) Homomorphism

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

$\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^nb^na^n \mid n \in \mathbb{N}\} = \psi(L')$ where

$\qquad \displaystyle \psi(x) = \begin{cases} a &x=a \lor x=c \\ b &x=b \end{cases}\quad\text{and}\quad L' = \{a^nb^nc^n \mid n \in \mathbb{N}\}.$

Therefore, because $L' \notin \mathrm{CFL}$ and $\mathrm{CFL}$ is closed against homomorphism and inverse homomorphism, $L \notin \mathrm{CFL}$.

Example 2: Intersection with Regular Languages

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}$.


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)
share|improve this answer
1  
@Raphael You should have look at Tomoyuki Yamakami's paper arxiv.org/abs/0808.4122 . It looks like Tomoyuki rediscovered a version of the interchanging lemma. He told me about his "swapping lemma" in Winter 2009. –  Dai Mar 29 '12 at 2:17
    
@Dai: I did not check the details (of the proofs), but it seems you are right. Thanks! (Too bad for him, though.) –  Raphael Mar 29 '12 at 6:37
    
@Raphael His application of the lemma is still very interesting though. –  Dai Mar 29 '12 at 14:09
    
There are nice closure properties of rich subclasses of CFL that can be used to the same effect. –  Raphael Apr 11 '13 at 7:16
add comment

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.

share|improve this answer
    
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
add comment

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:
  i) $d(vx) \geq 1$ and $e(vx) =0$
  ii) $d(vwx) \leq n^{e(vwx)+1}$ and
  iii) 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)$

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.