[Solved]: Structure of a Pumping Lemma proof: contradiction or counterexample?

Problem Detail: 

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact structure of a proof where you show a language is not regular or context-free?

Wikipedia and most proofs start with "Suppose $L$ is a regular language", which would mean it is a proof by contradiction, because it isn't.

But the lemma has the quantifiers $\exists, \forall, \exists, \forall$ in order. And in the proof you assume a given constant given by the first $\exists$, and then you come up with some word (the first $\forall$), format it in some given substring division (the second $\exists$) and again come up with some $k$ (second $\forall$) for which you show it is not in $L$.

This seems to me like a counterexample proof ("this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma"), and not a proof by contradiction?

Asked By : PHPirate

Answered By : Raphael

this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma

You are missing that in order to construct this counterexample you have to assume that $L$ is regular. Then you apply the Pumping lemma, which yields the Pumping length $p$. Only then do you construct your (counter)example string (using $p$!) and show that it contradicts the Pumping lemma. Hence, the assumption must be false.

So while you can say that you derive the contradiction using a counterexample, the outer-most proof is by contradiction.
With the assumption, you wouldn't have $p$!

Note that proofs can be nested, so you don't need to see only one proof technique. For instance, induction proofs often use a proof by contradiction inside the inductive step.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59309