Ogden's lemma: Difference between revisions
gen cleaning |
|||
| Line 1: | Line 1: | ||
In the theory of [[formal language]]s, '''Ogden's lemma''' (named after William F. Ogden) is a generalization of the [[pumping lemma for context-free languages]]. |
In the theory of [[formal language]]s, '''Ogden's lemma''' (named after William F. Ogden) is a generalization of the [[pumping lemma for context-free languages]]. |
||
== Statement == |
|||
Ogden's lemma states that if a language {{mvar|L}} is context-free, then there exists some number <math>p\geq 1</math> (where {{mvar|p}} may or may not be a pumping length) such that for any string {{mvar|s}} of length at least {{mvar|p}} in {{mvar|L}} and every way of "marking" {{mvar|p}} or more of the positions in {{mvar|s}}, {{mvar|s}} can be written as |
Ogden's lemma states that if a language {{mvar|L}} is context-free, then there exists some number <math>p\geq 1</math> (where {{mvar|p}} may or may not be a pumping length) such that for any string {{mvar|s}} of length at least {{mvar|p}} in {{mvar|L}} and every way of "marking" {{mvar|p}} or more of the positions in {{mvar|s}}, {{mvar|s}} can be written as |
||
:<math>s = uvwxy</math> |
:<math>s = uvwxy</math> |
||
| Line 10: | Line 11: | ||
In the special case where every position is marked, Ogden's lemma is equivalent to the pumping lemma for context-free languages. Ogden's lemma can be used to show that certain languages are not context-free in cases where the pumping lemma is not sufficient. An example is the language <math>\{a^i b^j c^k d^l : i = 0 \text{ or } j = k = l\}</math>. |
In the special case where every position is marked, Ogden's lemma is equivalent to the pumping lemma for context-free languages. Ogden's lemma can be used to show that certain languages are not context-free in cases where the pumping lemma is not sufficient. An example is the language <math>\{a^i b^j c^k d^l : i = 0 \text{ or } j = k = l\}</math>. |
||
Ogden's lemma can also be used to prove the [[Ambiguous grammar#Inherently ambiguous languages|inherent ambiguity]] of some languages{{Citation needed|reason=this is not trivial to see and requires a reference|date=September 2017}} |
Ogden's lemma can also be used to prove the [[Ambiguous grammar#Inherently ambiguous languages|inherent ambiguity]] of some languages.{{Citation needed|reason=this is not trivial to see and requires a reference|date=September 2017}} |
||
== Generalized |
== Generalized condition == |
||
Bader and Moura have generalized the lemma<ref>{{cite journal |last1=Bader |first1=Christopher |last2=Moura |first2=Arnaldo |title=A Generalization of Ogden’s Lemma |journal=Applied Mathematics and Computation |date=April 1982|volume=29 |issue=2 |pages=404-407 |doi=10.1145/322307.322315 |url=https://doi.org/10.1145/322307.322315 |accessdate=7 July 2020}}</ref> to allow marking some positions that are ''not'' to be included in {{mvar|vx}}. Their dependence of the parameters was later improved by Dömösi and Kudlek. If we denote the number of such ''excluded'' positions by {{mvar|e}}, then the number {{mvar|d}} of ''distinguished'' positions of which we want to include some in {{mvar|vx}} must satisfy <math>d\geq p(e+1)</math>, where {{mvar|p}} is some constant that depends only on the language. The statement becomes that every {{mvar|s}} can be written as |
Bader and Moura have generalized the lemma<ref>{{cite journal |last1=Bader |first1=Christopher |last2=Moura |first2=Arnaldo |title=A Generalization of Ogden’s Lemma |journal=Applied Mathematics and Computation |date=April 1982|volume=29 |issue=2 |pages=404-407 |doi=10.1145/322307.322315 |url=https://doi.org/10.1145/322307.322315 |accessdate=7 July 2020}}</ref> to allow marking some positions that are ''not'' to be included in {{mvar|vx}}. Their dependence of the parameters was later improved by Dömösi and Kudlek. If we denote the number of such ''excluded'' positions by {{mvar|e}}, then the number {{mvar|d}} of ''distinguished'' positions of which we want to include some in {{mvar|vx}} must satisfy <math>d\geq p(e+1)</math>, where {{mvar|p}} is some constant that depends only on the language. The statement becomes that every {{mvar|s}} can be written as |
||
| Line 30: | Line 31: | ||
== References == |
== References == |
||
{{Reflist}} |
{{Reflist}} |
||
| ⚫ | |||
| ⚫ | |||
* {{cite journal | author=Ogden, W. | title=A helpful result for proving inherent ambiguity | journal=Mathematical Systems Theory | volume=2 | year=1968 | pages=191–194 | doi=10.1007/BF01694004 | issue=3}} |
|||
| ⚫ | |||
== Further reading == |
|||
{{Formal languages and grammars |state=collapsed}} |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
[[Category:Formal languages]] |
[[Category:Formal languages]] |
||
Revision as of 23:12, 23 July 2020
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.
Statement
Ogden's lemma states that if a language L is context-free, then there exists some number (where p may or may not be a pumping length) such that for any string s of length at least p in L and every way of "marking" p or more of the positions in s, s can be written as
with strings u, v, w, x, and y, such that
- vx has at least one marked position,
- vwx has at most p marked positions, and
- for all .
In the special case where every position is marked, Ogden's lemma is equivalent to the pumping lemma for context-free languages. Ogden's lemma can be used to show that certain languages are not context-free in cases where the pumping lemma is not sufficient. An example is the language . Ogden's lemma can also be used to prove the inherent ambiguity of some languages.[citation needed]
Generalized condition
Bader and Moura have generalized the lemma[1] to allow marking some positions that are not to be included in vx. Their dependence of the parameters was later improved by Dömösi and Kudlek. If we denote the number of such excluded positions by e, then the number d of distinguished positions of which we want to include some in vx must satisfy , where p is some constant that depends only on the language. The statement becomes that every s can be written as
with strings u, v, w, x, and y, such that
- vx has at least one distinguished position and no excluded position,
- vwx has at most distinguished positions, and
- for all .
Moreover, either each of u,v,w has a distinguished position, or each of has a distinguished position.
See also
References
- ^ Bader, Christopher; Moura, Arnaldo (April 1982). "A Generalization of Ogden's Lemma". Applied Mathematics and Computation. 29 (2): 404–407. doi:10.1145/322307.322315. Retrieved 7 July 2020.
Further reading
- Dömösi, P.; Kudlek, M. (1999). "Strong Iteration Lemmata for Regular, Linear, Context-Free, and Linear Indexed Languages". FCT'99, LNCS. 1684: 226–233. doi:10.1007/3-540-48321-7_18.
- Ogden, W. (1968). "A helpful result for proving inherent ambiguity". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/BF01694004.
- Hopcroft; Motwani; Ullman (1979). Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 81-7808-347-7.