Hi Math Stack Exchange,

Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37):

If L is a context-free language, there exists a number k such that any string $s ∈ L$, if $|s| ≥ k$, then we can write $s = uvxyz$ where

  1. for each $i ≥ 0$, $uv^ixy^iz \in L$
  2. $v \neq \varepsilon$ and $y \neq \varepsilon$
  3. $|vxy| ≤ k.$

I tried modifying the original proof of the he pumping lemma, attempting to exploit the structure of parse trees. First, put the grammar in Chompsky normal form, so the parse tree is a binary tree. If the word is big enough, there is a sequence

$$ V_0, V_1, \dots, V_n $$

Such that $V_i$ is the parent of $V_{i+1}$ in the parse tree. If $n$ is made big enough, then some variable repeats itself. Provided that we take left and right derivations, we obtain nonempty $v$ and $y$ to pump. I am left with the case where we only take left derivations, or only take right derivations. I assume there's some trick at this point, but I've given it a few hours thought and can't come up with anything. Any hints?

  • $\begingroup$ what do you mean by taking only left (or right) derivation? since your tree is the parse tree of a word of your language you must derive all non terminal symbols, no? If your problem is when the derivation give you an empty $v$ or $y$, the solution is to consider words larger than $k$ where $k$ is the longest word you can obtain without such branches in the parse tree. This will give you the existence of a branch with the required property. $\endgroup$
    – wece
    Feb 17, 2016 at 12:37
  • 1
    $\begingroup$ Here's an example. Consider the language $\{ 0^n : n \geq 0 \}$, with context free grammar $A \rightarrow xA | x$. Surely A repeats itself, but it only takes right branches to get to itself, so only pumps out characters to the left of itself. There is no limit to the number of branches with this property, unless I'm misunderstanding you. $\endgroup$ Feb 17, 2016 at 17:17
  • $\begingroup$ @wece from Sipser 3rd edition p 108: a derivation "is a leftmost derivation if at every step the leftmost remaining variable is the one replaced". $\endgroup$
    – xdavidliu
    Jul 24, 2020 at 22:48
  • $\begingroup$ The "and" is wrong, it can certainly happen that $v$ or $y$ are empty, just not both. $\endgroup$
    – vonbrand
    Sep 7, 2023 at 13:08

1 Answer 1


Found the trick to finish the proof. We just need to increasing the size of the pump. Let $v$ be the number of variables in a Chompsky normal form grammar. If $2^v$ is the ordinary pumping length. Consider a new length $2^{3v}$. In the parse tree of a long string (of minimal length) of length greater than $2^{3v}$, there must be a path of height $3v$. Thus some variable must occur 3 times. Then use the minimality of the parse tree to conclude that the stepwise retiteration can be pumped.

  • $\begingroup$ it's unclear what "Then use the minimality of the parse tree to conclude that the stepwise retiteration can be pumped." means... $\endgroup$
    – xdavidliu
    Jul 25, 2020 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .