上下文無關語言的性質

上下文無關語言的幫浦常數(pumping constant)

每個幫浦引理都附帶一個門檻:一個長度 p,使得「一旦」語言中的字串至少這麼長,可抽取的結構就保證出現。對上下文無關語言來說,這個門檻就是幫浦常數。低於它,短字串可能沒有任何可重複的部分;達到或超過它,重複就被「逼出來」——而這個被逼出的重複,正是引理所利用的。

p 從哪裡來?把語言的文法化為喬姆斯基正規形式(Chomsky normal form),其中每條規則產生兩個變數或一個終端符號,所以剖析樹是「二元」的。若文法有 b 個變數(非終端符號),一棵最長「根到葉」路徑長度至多為 b 的剖析樹,最多產出長度 2^(b-1) 的字串。所以取 p = 2^b(或任何大於「路徑受限的樹」最長產出的值)。那麼任何長度 >= p 的字串,其剖析樹必有一條超過 b 個節點的路徑,而在標有超過 b 個節點的路徑上,某個「變數」必定重複——這就是鴿籠那一步。重複的變數正好給出 u v x y z' 的切法,而 v x y 保持短(受 p 約束),因為它是那條路徑底部附近一棵有界子樹的產出。

實務上你幾乎從不去算出 p。引理只說「存在某個」p;在證明裡你把它當成一個未知的固定數,挑一個長度取決於 p 的字串(這樣就保證夠長),然後在從不釘死 p 的情況下導出矛盾。這個常數是概念上的鷹架——它的「存在」(追溯到 CNF 文法中有限個變數)才是重點;它確切的數值很少要緊。

若一個 CNF 文法有 b = 4 個變數,取 p = 2^4 = 16。其語言中任何長度 16 或以上的字串,在任何剖析樹裡,都必有一條「根到葉」路徑重複了那 4 個變數之一——由鴿籠原理,因為該路徑有超過 4 個被標記的內部節點。這個重複給出可抽取的 u v x y z' 分解。

p 與喬姆斯基正規形式剖析樹的高度相連:路徑上夠多的變數逼出其中之一重複。

p 取決於文法、而不只是語言,而你很少需要它的確切值——證明把它當成「固定但未知」的常數。它之所以存在,是因為 CNF 文法只有有限個變數。

又稱
pumping length for CFLsthe constant pCFL 幫浦長度常數 p