In the theory of formal languages, Ogden's lemma is a generalization of the lemma pumping for context-free languages.

Ogden's Lemma states that if L is a context-free language then there exists an entire p & gt; 0 such that for each z string of length at least p in L and any way of "marking" p or multiple positions within z, we can write z as z = uvwxy

where u, v, w, x, and y strings meet the following conditions:

In the particular case where all z positions are marked, this result is reduced to the panning of lemma for context-free languages.

Ogden's lemma allows to demonstrate the non-belonging of certain languages ​​to the class of free languages ​​from the context, even in some cases where the pumping lemma is not enough. An example is the language {abcd: i = 0 or j = k = l}. It is also useful to demonstrate the inherent ambiguity of some languages. Voices correlateemodify wikitesto Refer to the wikitesto tag

wiki