Ogden's lemma

Choose a context-free grammar $G_0$ with $L(G_0)=L$ by [L2], then replace it by an equivalent Chomsky-normal-form grammar $G=(V,\mathrm{\Sigma },P,S)$ by [L3]. Set $p:=2^{\mathrm{\mid }V\mathrm{\mid }+1}$. Let $z\in L$ and mark at least $p$ positions of $z$. Because $p\ge 1$, the word $z$ is nonempty, so by [L4] fix a parse tree $T$ for $z$ in the CNF grammar $G$.

Starting at the root of $T$, build a path to a marked leaf by always moving to a child whose subtree contains the larger number of marked positions; when both children contain marked positions, choose one of the heavier children. Call such a node a branch point. Each time the path passes through a branch point, the chosen child still contains at least half of the marked positions seen at that node. Therefore, if there were at most $\mathrm{\mid }V\mathrm{\mid }$ branch points on the path, the terminal leaf at the end would still lie below at least $p\mathrm{/}{2}^{\mathrm{\mid }V\mathrm{\mid }}=2$ marked positions, impossible for one leaf. So the path contains at least $\mathrm{\mid }V\mathrm{\mid }+1$ branch points.

Among the last $\mathrm{\mid }V\mathrm{\mid }+1$ branch points on that path, choose two with the same variable label $A$, with the upper one above the lower one. Let the lower $A$-subtree yield $w$, and let the material in the upper $A$-subtree to the left and right of the lower subtree yield $v$ and $x$, so that the whole word is $z=uvwxy$. The upper branch point has marked material outside the lower subtree, so the concatenation $vx$ contains a marked position. Also, if the upper $A$-subtree contained more than $2^{\mathrm{\mid }V\mathrm{\mid }}$ marked positions, then repeating the branch-point-halving argument inside that subtree would produce more than $\mathrm{\mid }V\mathrm{\mid }$ branch points below it on the chosen path, contradicting that we selected the upper $A$ among the last $\mathrm{\mid }V\mathrm{\mid }+1$ branch points. Hence $vwx$ contains at most $2^{\mathrm{\mid }V\mathrm{\mid }}<p$ marked positions. By [L1], the decomposition is $p$-admissible.

The upper occurrence of $A$ derives the lower one by a derivation segment $A{\Rightarrow }^{\ast }vAx$, and the lower subtree derives $w$. Repeating or deleting that segment while keeping the rest of the parse tree fixed produces derivations of $u{v}^{i}w{x}^{i}y$ for every $i\ge 0$. Therefore every such word lies in $L(G)=L$.

Hence the integer $p$ satisfies Ogden's lemma for $L$.