2 of 6
Gave an example
jmad
  • 9.3k
  • 1
  • 36
  • 41

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 rewrite 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.

jmad
  • 9.3k
  • 1
  • 36
  • 41