Ogden's lemma
Encyclopedia
In the theory of formal language
s, Ogden's lemma (named after William F. Ogden) provides an extension of flexibility over the pumping lemma
for context-free language
s.
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
with strings u, x, y, z, and v, such that
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 {aibjckdl : i = 0 or j = k = l}.
It is also useful to prove the inherent ambiguity of some languages.
Observe that when every position is marked, this lemma is equivalent to the pumping lemma for context-free languages.
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, Ogden's lemma (named after William F. Ogden) provides an extension of flexibility over the pumping lemma
Pumping lemma
In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of...
for context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s.
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 = uxyzv
with strings u, x, y, z, and v, such that
- xz has at least one marked position,
- xyz has at most p marked positions, and
- uxiyziv 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
Pumping lemma for context-free languages
The pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages.- Formal statement :...
is not sufficient. An example is the language {aibjckdl : i = 0 or j = k = l}.
It is also useful to prove the inherent ambiguity of some languages.
Observe that when every position is marked, this lemma is equivalent to the pumping lemma for context-free languages.
See also
- Pumping lemma for context-free languagesPumping lemma for context-free languagesThe pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages.- Formal statement :...
- Pumping lemma for regular languagesPumping lemma for regular languagesIn the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped — that is, have a middle section of the word repeated an arbitrary number of...