1樓：
上下文無關語言(CFL)的幫浦引理其實跟正則語言(RL)的幫浦引理本質是一樣的，都是通過鴿巢原理來證明的。而且只要找對思考這個問題的角度，其實它是很簡單並且符合直覺的。
舉個例子，理解正則語言的角度可以是確定性有窮自動機(DFA)，也可以是非確定性有窮自動機(NFA)，還可以是正規表示式(RE)。而我們選擇哪乙個模型，則取決於具體的場景。比如，如果我們要證明正則語言的補仍然是正則語言，我們就從DFA的角度來理解，因為只需要將原DFA的接受狀態集和非接受狀態集對調就行了；而如果我們要證明正則語言的並集或者連線仍然是正則的，那從NFA的角度來理解就方便多了， 因為NFA提供了非確定性的「猜測」的功能。
回到幫浦引理。首先對於正則語言來說，我們要證明幫浦引理，從DFA的角度出發就行了。由於DFA的狀態數有限，並且DFA每讀乙個字元都要做狀態的轉移，那當字串的長度達到DFA的狀態數時，必然會出現某個狀態至少被訪問兩次的情況。
(鴿巢原理)從圖形上講，DFA處理該字串時的接受路徑，就包含了乙個環，這個環就對應我們要「幫浦」的那個子串。不管你將該子串重複多次還是捨去，在DFA的圖形上講，不過是添環或者刪環的操作罷了，整個字串仍然對應有一條接受路徑。
而就上下文無關語言來說，我們要證明幫浦引理，應該從上下文無關文法(CFG)而不是下推自動機(PDA)的角度來理解。因為CFG的變數數是有限的，並且變數每次根據某個規則派生時引入的終結符(terminals)數量是有限的，那當由終結符構成的字串長度超過某個值(pumping length)時，必然出現某個變數至少被派生了兩次的情況。那這裡的某個值應該取多少呢？
假設單項派生規則所能引入的終結符數量最多為M，變數數為N，那我們pumping length取 就行了。超過上述pumping length的字串對應的語法分析樹結構就如下圖，從根節點到葉節點的路徑中，必然有一條包含重複變數R。於是我們可以把下面那個R對應的子樹替換成上面R對應的子樹或者反過來，對應於之前正則語言幫浦引理的添環或者刪環的操作。
（求pumping length時，Sipser的書裡考慮的是與派生過程對應的語法分析樹。因為變數所能派生的最大分支數是固定的，並且字串對應葉節點，那當字串的長度超過某個值時，語法分析樹的高度必然超過變數數，原理還是一樣的。）
2樓：Sqd You
我學的這個「CF的幫浦引理」是叫做uvwxy定理，然後才知道一般說的正則幫浦引理是uvwxy定理的特化，或者說uvwxy定理是正則幫浦引理的推廣。
結合最近的梗，uvwxy定理其實是在禁止套娃。
套娃是什麼意思呢，假設我們有這個簡單的CF語法：
S → A
A → aA | b
不聰明的小朋友也可以看出，通過A的套娃，我們可以產生形如aaa.....aaaab這樣的字串。禁止套娃指的就是一條規則只能用一次，也就把我們能產生的字串限定在了 這個小小的集合內。
我們直覺上容易看出，如果禁止套娃，那麼乙個CF語法生成的字串長度是有上限的。畢竟生成規則的個數是有限的，在用過了所有規則以後，只有套娃才能讓字串在紙上無限延申。所以團長，不要停下來啊（劃掉
既然禁止套娃能生成的字串長度是有限的，不如把最長的非套娃字串的長度表示為L，例如上例中L=2。uvwxy定理說：所有長度大於L的字串（他們自然全都是套娃字串了）都可以被分解為uvwxy五個部分，其中u和y是無關緊要的前字尾，而vwx是乙個套娃：
v和x是套子，w是娃。
vwx是套娃是什麼意思呢，意思是形如uvwxy，uv(vwx)xy，uv(v(vwx)x)xy，uv(v(v(vwx)x)x)xy這樣的套娃全都可以通過這個語法生成。這些套娃的通式是 。可以看出w是中心的那個最小的娃，它兩旁的一層又一層的v..
x組成了一層又一層的套娃。
證明請看另乙個回答。
那麼怎麼把它收斂到我們一般說的正則幫浦引理（uvw定理）呢？我們注意到對於正則語法，x和y必須是空的（等於 ）。因為我們既然能夠對vwx進行套娃，那就說明這個套娃裡在某個時間點存在non terminal，而正則語法不允許non terminal右側有東西。
換句話說，uvwxy定理收斂到了 ，也就是正則幫浦引理/uvw定理。
3樓：SoulFlow
大概記得，簡單說你構造的DFA的乙個計算的狀態轉移序列滿足抽屜原理，
應用就是反證法證非正則語言
建議看edX上北大的理論電腦科學概論理論電腦科學基礎課程，或者Sipser的《計算理論導引》。
4樓：
Pumping Lemma for CFL 簡單來講，對於乙個符合某 CFL 的字串，你可以按照規則重複（"pump"）其中的若干部分，得到的新字串依然屬於這個 CFL。Pumping Lemma 一般用於反證某種語言不是 RL 或 CFL，所以一般用作 Lemma 而非 Theorem。
Sipser 2.3 裡介紹了 Pumping Lemma for CFL 的證明，其思路如下：
在乙個語言 A 中構建乙個足夠長的字串 s，那麼 s 就可以通過 A 對應的語法 G 來 parse 成乙個 parse tree。所謂足夠長的意思是，這個 parse tree 上會有一些足夠長的從樹根到葉的路徑，根據鴿籠原理，這個路徑上某些 non-terminal symbol，比如 N 會出現不止一次。你把子節點上的乙個 N 替換成乙個根節點上同構的 N，就相當於把字串中間的某些部分重複了，這樣 pumping 出來的新字串依然符合其語法，也即依然在語言 A 中。
這就對應了維基的配圖（Sipser 中的配圖也差不多）：
Pumping Lemma for CFL 把字串分為五部分，是因為頭尾 uy 和中間 w 是不動點（當然它們是可空的），而乙個 CFL 的替換規則可以是形如
A → aAb
的形式，其中大寫字母是 non-terminal，小寫字母是 terminal。乙個 parse tree 上的乙個節點按照這樣的規則展開自己的時候，會同時在前後新增給定的片段（其一可以為空，但不能同時為空），所以在 lemma 的表述中 v 和 x 重複的次數是相同的。圖中的例子，A 就是圖中的 N，a 就是 v，b 就是 x，你同時重複 v 和 x，就是在 parse tree 上不斷替換 N 下面的結構。
怎麼用？一般的做法是，給你乙個語法，你窮舉所有把這個語法拆成 vwx 的模式（雖然比 Pumping Lemma for RL 的模式多，但其實也沒多少），然後證明所有這些拆法都不行，所以這個語言不是 CFL。例子有很多，比方這個。
如何直觀地理解Sublattice symmetry和Particle hole symmetry？
拋磚引玉，sublattice比如說石墨烯的，P H比如說各種half filling系統，超導之類的。反正只要是對稱性就行，然後一維的系統的拓撲是根據這種對稱性算符的表示來分類的 一維只有SPT 所以就是這麼影響的吧2333 匿了匿了，對這種問題不知道如何下筆 回到SPT來，那麼對稱性是怎麼影響這...
如何直觀地理解 Spence Mirrlees Single crossing condition
垃圾 sleepsoft 講到了任何形式的single crossing 基本上都是為了保證解的某種性質而要求的，Richard Xu 則具體講了一些性質和應用。講的非常好而且基本上把能講的都講了，我再隨便逼逼兩句。In most cases,some variation of single cro...
如何直觀地理解 共軛 這個概念？
共軛是一種特殊的二元對稱關係，如果兩個同類或者具有同等性質的物件或元素可以通過一種操作或者同類操作可以同時來回變換，就稱它們具有共軛關係。對偶不是一種操作或同類操作可以轉換的，也不是同時來回變換的，也不必用在同一種物件之間 如射影幾何中的點和線 共軛是一種代數的概念，類似於幾何中的垂直或正交概念，垂...