查看“︁鄂登引理”︁的源代码

在[[形式语言]]理论中，'''Ogden引理'''提供了在[[上下文无关语言]]的[[泵引理]]上灵活性的扩展。

Ogden 引理声称如果语言 ''L'' 是上下文无关的，则存在某个数 ''p'' > 0 (这里的 ''p'' 可以是也可以不是抽吸长度)，使得对于 ''L'' 中任何长度至少 ''p'' 字符串 ''w''，和“标记” ''p'' 或更多个 ''w'' 中的位置的所有方式，''w'' 可以被写为
:''w'' = ''uvxyz''
带有字符串 ''u'', ''v'', ''x'', ''y'' 和 ''z''，使得 ''vy'' 有至少一个标记了的位置，''vxy'' 有最多 ''p'' 个标记了的位置，而
:<math>uv^ixy^iz</math> 在 ''L'' 中，对于所有 <math>i\ge 0</math>。

Ogden 引理可以在[[上下文无关语言]]的[[泵引理]]不充分的情况下，被用来证明特定语言不是上下文无关的。一个例子是语言 <math>\{ a^ib^jc^kd^l : i=0 \ \text{或} \ \ j=k=l\}</math>。

观察到在所有位置都被标记了的时候，这个引理等价于上下文无关语言的泵引理。

== 参见 ==
* [[泵引理]]

== 引用 ==
* {{cite journal | author=Ogden, W. | title=A helpful result for proving inherent ambiguity | journal=Mathematical Systems Theory | volume=2 | year=1968 | pages=191-194}}
* {{cite book|author = Hopcroft, Motwani and Ullman | year = 1979 | title = Automata Theory, Languages, and Computation |url = https://archive.org/details/trent_0116301269779 | publisher = Adison Wesley}}

[[Category:形式语言|E]]
[[Category:引理]]