Ogden's Lemma

A generalized Pumping Lemma.

Lemma

• If Language $L$ is generated by a CFG
• Then $\exists p\ge 1$ s.t $\forall w\in L$ with length $>p$, a way of marking $\ge p$ positions, there exist Non-terminal $A$ and a way to split $w$ into 5 segments $uxzyv$ s.t:
  • $S{\Rightarrow }^{\ast }uAv{\Rightarrow }^{\ast }uxAyv{\Rightarrow }^{\ast }uxzyv$
• $x$ contains atleast one marked position
• $xyz$ contains at most $p$ marked positions
• $u,z$ contains marked positions or $y,v$ both contain marked positions.