Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language.

A regular language can be recognized by a finite automaton. All words are recognized through:

• either a finite path through the automaton: words that are shorter than the pumping length;

• or a path that goes through a node at which there is a loop, in which case it is possible to go through the loop any number of times: that's the $y^n$ part, where $y$ is the path through one round of the loop and $n$ is the number of lops.

A context-free language can be recognized by a pushdown automaton. All words are recognized through:

• either a finite path through the automaton: words that are shorter than the pumping length;

• or a path that includes both a loop with pushes to the stack, and another loop with corresponding pops. Pushes and pops have to balance in order to get an empty stack at the end. Then the word contains a loop with pushes $v$, some further path $w$, and a loop with pops $x$. The number of runs through the two loops has to be the same, but it can be any number, hence the middle bit $v^n w x^n$.

You can also get a similar intuition from the ways regular and context-free languages can be specified by a regular expression and a context-free grammar respectively.

If a word is recognized by a regular expression, then:

• either the word does use a part of the expression under the $^*$ (Kleene star) operator, and that part $y$ can be repeated any number of times;

• or the word doesn't use any part of the expression under a star, and it can't be longer than the expression itself.

If a word is recognized by a context-free grammar, then:

• It may be that the word is recognized by a parse tree where there is a subtree $\mathcal{T}_1$ which is recognized by the nonterminal $A$, and a subtree $\mathcal{T}_0$ of that subtree is recognized by the same nonterminal $A$. In that case, let $w$ be the part of the word that is recognized by $\mathcal{T}_0$ and $vwx$ be the part that is recognized by $\mathcal{T}_1$. You also get a valid parse tree if you replace $\mathcal{T}_1$ by $\mathcal{T}_0$ or vice versa. Furthermore, since $\mathcal{T}_1$ contains $\mathcal{T}_0$, after replacing $\mathcal{T}_0$ by $\mathcal{T}_1$, you can replace the copy of $\mathcal{T}_0$ inside $\mathcal{T}_1$ by $\mathcal{T}_1$, and so on. This means that you can replace $vwx$ by $w$, $v^2wx^2$, $v^3wx^3$, etc. and still get a word with a valid parse tree.

• Otherwise, there is no subtree of the parse tree which reuses the same nonterminal, and in that case the length of the word is bounded because the depth of the parse tree is bounded by the number of nonterminals in the grammar.

StackExchange Computer Science Q#93391, answer score: 13