Ogden's lemma

In the theory of formal languages, Ogden's lemma (named after William F. Ogden) 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. 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.