鄂登引理

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

Ogden 引理声称如果语言 L 是上下文无关的，则存在某个数 p > 0 (这里的 p 可以是也可以不是抽吸长度)，使得对于 L 中任何长度至少 p 字符串 w，和“标记” p 或更多个 w 中的位置的所有方式，w 可以被写为

w = uvxyz

带有字符串 u, v, x, y 和 z，使得 vy 有至少一个标记了的位置，vxy 有最多 p 个标记了的位置，而

${\displaystyle uv^{i}xy^{i}z}$ 在 L 中，对于所有 ${\displaystyle i\geq 0}$。

Ogden 引理可以在上下文无关语言的泵引理不充分的情况下，被用来证明特定语言不是上下文无关的。一个例子是语言 ${\displaystyle \{a^{i}b^{j}c^{k}d^{l}:i=0\ {\text{或}}\ \ j=k=l\}}$。

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