鄂登引理

在形式語言理論中，Ogden引理提供了在上下文無關語言的泵引理上靈活性的擴展。

Ogden 引理聲稱如果語言 L 是上下文無關的，則存在某個數 p > 0 (這裡的 p 可以是也可以不是抽吸長度)，使得對於 L 中任何長度至少 p 字符串 w，和「標記」 p 或更多個 w 中的位置的所有方式，w 可以被寫為

w = uvxyz

帶有字符串 u, v, x, y 和 z，使得 vy 有至少一個標記了的位置，vxy 有最多 p 個標記了的位置，而

$uv^{i}xy^{i}z$ 在 L 中，對於所有 $i\geq 0$。

Ogden 引理可以在上下文無關語言的泵引理不充分的情況下，被用來證明特定語言不是上下文無關的。一個例子是語言 $\{a^{i}b^{j}c^{k}d^{l}:i=0\ {\text{或}}\ \ j=k=l\}$。

觀察到在所有位置都被標記了的時候，這個引理等價於上下文無關語言的泵引理。

參見

• 泵引理

引用

• Ogden, W. A helpful result for proving inherent ambiguity. Mathematical Systems Theory. 1968, 2: 191–194. 
• Hopcroft, Motwani and Ullman. Automata Theory, Languages, and Computation. Adison Wesley. 1979.