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
- for each $i ≥ 0$, $uv^ixy^iz \in L$
- $v \neq \varepsilon$ and $y \neq \varepsilon$
- $|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?