OGDEN'S LEMMA

In the theory of formal languages, 'Ogden's lemma' provides an extension of flexibility over the pumping lemma for context-free languages.
Ogden's lemma states that if a language ''L'' is context-free, then there exists some number ''p'' > 0 (where ''p'' may or may not be a pumping length) such that for any string ''w'' of length at least ''p'' in ''L'' and every way of "marking" ''p'' or more of the positions in ''w'', ''w'' can be written as
:''w'' = ''uvxyz''
with strings ''u'', ''v'', ''x'', ''y'', and ''z'', such that ''vy'' has at least one marked position, ''vxy'' has at most ''p'' marked positions, and
:''uvⁱxyⁱz'' is in ''L'' for every ''i'' ≥ 0.
Ogden's lemma can be used to show that certain languages are not context-free, in cases where the pumping lemma for context-free languages is not sufficient. An example is the language {''aⁱb^jc^kd^l'' : ''i'' = 0 or ''j'' = ''k'' = ''l''}.
Observe that when every position is marked, this lemma is equivalent to the pumping lemma for context-free languages.

Contents

See also

References

See also

★ Pumping lemma

★ Pumping lemma for context-free languages

★ Pumping lemma for regular languages

References

★ A helpful result for proving inherent ambiguity, Ogden, W., , , Mathematical Systems Theory, 1968

★ Automata Theory, Languages, and Computation, Hopcroft, Motwani and Ullman, , , Adison Wesley, 1979,