上下文無關語言的性質

上下文無關語言對交集不封閉(not closed under intersection)

下推自動機(PDA)只有一個堆疊(stack)——像一疊盤子,你只能碰最上面那個。這一個堆疊足以核對「一」對必須相等的東西,例如 a^n b^n 裡的 a 與 b:每個 a 推入一個標記、每個 b 彈出一個。但交集暗地裡要求一台機器「同時」執行「兩」個計數條件,而一個堆疊無法獨立記兩筆帳。這就是為什麼把兩個上下文無關語言取交集,可能會把你帶到家族「之外」的核心原因。

標準反例用三個字母。設 L1 = { a^n b^n c^m : n, m >= 0 }——a 的個數必須等於 b 的個數,c 則自由。這是上下文無關的:一台 PDA 用堆疊把 a 對上 b、忽略 c。設 L2 = { a^m b^n c^n : n, m >= 0 }——這次是 b 必須等於 c、a 自由;由對稱的機器也知它是上下文無關。它們的交集 L1 ∩ L2 同時逼出 a=b「且」b=c,這表示三者個數全相等:{ a^n b^n c^n : n >= 0 }。這個語言可被證明「不」是上下文無關(幫浦引理會打垮它)。所以兩個 CFL 取交集得到了一個非 CFL——家族對交集不封閉。

為什麼一個堆疊的圖像能解釋這件事?要核對 a^n b^n c^n,機器得在比對 b 的同時記住 a 的個數,然後「還要」保有那個個數去比對 c——但為了比對 b 而把堆疊彈空,就已經摧毀了比對 c 所需的紀錄。封閉性失敗,正是 PDA 單一堆疊記憶的直接投影。一台有兩個堆疊的機器辦得到,但兩個堆疊已經等同於圖靈機(Turing machine)的完整能力,遠遠超出上下文無關。

L1 = { a^n b^n c^m }(上下文無關)與 L2 = { a^m b^n c^n }(上下文無關)。它們的交集是 { a^n b^n c^n }(非上下文無關)。兩個俱樂部成員組合出一個非成員——這就證明了家族對交集不封閉。

兩個 CFL,其交集是非上下文無關的語言 a^n b^n c^n。

對交集不封閉「不」表示交集總是非 CFL——有時它仍是。它只表示家族不「保證」封閉:一個反例就足以推翻封閉性。

又称
non-closure under intersectionCFL 交集不封閉