Ogden’s Lemma for CFL Ogden’s Lemma:


Let L be an infinite Context Free Language, then there exists some positive integer n


Such that for any string ω ∊ L with |ω| ≥ n, and if we mark at least n positions in ω as distinguished, then we can write ω = uvxyz.


Such that :


  • x has at least one marked position.


  • v and y together contain at least one distinguished position.


  • vxy has at most n distinguished position.



Use of Ogden’s Lemma: 


Ogden’s lemma can be used to prove the given languages are not Context Free Language, in that case where pumping lemma for CFL fails. 





It is not CFL. This proves is not possible for pumping lemma.