= Three-block context-free pumping obstruction
The <pumping lemma for context-free languages> rules out a <formal language> when two pumpable pieces cannot preserve all three linked block counts. For example, let $L=\{a^nb^nc^n:n\geq0\}$. If $L$ were a <context-free language> with <pumping length> $p$, the <word> $a^pb^pc^p$ would have a decomposition $uvxyz$ with $|vxy|\leq p$ and $|vy|>0$.
The window $vxy$ cannot contain both an $a$ and a $c$, because the intervening $b$ block alone has length $p$. Pumping down to $uxz$ therefore leaves at least one outer block at length $p$, while deleting at least one symbol from another block. The remaining block counts cannot all be equal, so $uxz\notin L$, contrary to the <pumping lemma for context-free languages>. This argument uses a necessary condition for <context-free languages>; satisfying a pumping condition would not itself prove that a <formal language> is a <context-free language>.
Back to article page