鄂登引理

簡介

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

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

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

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

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

在數學、邏輯和計算機科學中，形式語言（英語：Formal language）是用精確的數學或機器可處理的公式定義的語言。

如語言學中語言一樣，形式語言一般有兩個方面:語法和語義。專門研究語言的語法的數學和計算機科學分支叫做形式語言理論，它只研究語言的語法而不致力於它的語義。在形式語言理論中，形式語言是一個字母表上的某些有限長字元串的集合。一個形式語言可以包含無限多個字元串。

上下文無關語言是可以用上下文無關文法定義的形式語言。所有上下文無關語言的集契約一於下推自動機所接受的語言的集合。

在可計算性理論中的形式語言理論中，泵引理聲稱給定類的任何語言可以被“抽吸”並仍屬於這個類。一個語言可以被抽吸，如果在這個語言中任何足夠長的字元串可以分解成片段，其中某些可以任意重複來生成語言中更長的字元串。這些引理的證明典型的需要計數論證比如鴿籠原理。

兩個最重要例子是正則語言的泵引理和上下文無關語言的泵引理。鄂登引理是另一種更強的上下文無關語言的泵引理。

這些引理可以用來確定特定語言不在給定語言類中。但是它們不能被用來確定一個語言在給定類中，因為滿足引理是類成員關係的必要條件，但不是充分條件。

泵引理是1961年由Y. Bar-Hillel、M. Perles和E. Shamir首次發表的。