This is an example of what is required in a proof, without extra explanations.
Exercise: Prove that the language L = {(ab)^n | n is prime} is not context-free.
Proof:
I use the pumping lemma for context-free languages.
Let n be any natural number.
I choose the word z = (ab)^m, where m is the smallest prime bigger than n.
Let z = uvwxy, |vx|>0, and |vwx|<=n.
I consider two cases:
- v has an equal number of a's as b's (so v is of the form (ab)^p or (ba)^p),
and the same holds for x: (ab)^q or (ba)^q.
Note that p+q>0.
I choose i = m:
in this case, uv^iwx^iy=(ab)^(m+ip+iq)=(ab)^(m*(1+p+q)) which is not in L, because both m and 1+p+q are integers bigger than 0, so m*(1+p+q) is not prime.
- either v, x, or both do not have the same number of a's as b's.
This means that v or x starts and ends in the same letter.
I choose i=2.
The word uvvwxxy is not of the form (ab)^m for any number m,
because there will be consecutive a's or b's on either the border of v and v, or the border of x and x.
It follows that the word is also not in L.
Since the pumping lemma does not hold in either case, L is not context-free.