Ogden's lemma

In the theory of formal languages, Ogden's lemma (named after William F. Ogden)[1] is a generalization of the pumping lemma for context-free languages.

Despite Ogden's lemma being a strengthening of the pumping lemma, it is insufficient to fully characterize the class of context-free languages.[2] This is in contrast to the Myhill-Nerode theorem, which unlike the pumping lemma for regular languages is a necessary and sufficient condition for regularity.

  1. ^ Ogden, William (September 1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/bf01694004. ISSN 0025-5661. S2CID 13197551.
  2. ^ Kracht, Marcus (2004). Too Many Languages Satisfy Ogden's Lemma (PDF). Proceedings of the 27th Pennsylvania Linguistics Colloquium. Philadelphia. pp. 115–121. Retrieved 16 May 2024.