巢狀結構與有限狀態限制
上下文無關文法可表達遞歸巢狀結構,有限自動機則可用有限個狀態實施條件。兩者的交集可同時實施這兩項要求。這個封閉結果有其特殊性:兩個任意上下文無關語言的交集未必上下文無關。我們會構造文法,包括空字串的規則,並雙向證明它的意義。
令 為有限上下文無關文法。每條產生式左邊是一個變元,右邊是有限的變元與終結符序列;右邊也可以為空。有限分析樹在每個變元節點套用一條產生式,其終結符葉由左至右讀出所得字串稱為產出。令 為確定有限自動機,狀態集 有限,轉移函數 處處有定義。以 表示從狀態 讀入字串 後到達的狀態,且 。
目標是構造 的文法:其字串必須由文法推導,並令自動機由 到達 中的狀態。此構造不要求文法具有特定範式,也不依賴現成的文法至堆疊轉換。
記錄進入與離開狀態的變元
定義 7.1.1
(進出變元)
對每個 及 ,引入變元 。它的預期語言恰由那些能從 的 推導、並使自動機由 到達 的終結字串 組成。加入新的起始變元 ,並對每個 加入規則 。若 為空, 沒有這類規則,所構造語言便為空。
定義 7.1.2
(相容狀態序列與乘積規則)
對每條原產生式 ,其中每個 是變元或終結符,考慮每個狀態序列 。若每當終結符 時,DFA 轉移都滿足 ,便稱此序列相容。對每個相容序列加入
其中若 是變元,則 ;若它是終結符,則 。對空產生式 ,為每個 加入 ,不加入進出狀態不同的空規則。由於 和 有限、每條右邊長度有限,所得規則數有限,但可能隨該長度及 迅速增長。
構造為何正確
引理 7.1.3
(進出變元的意義)
對每個 、所有 及每個終結字串 ,變元 在所構造的文法中能推導 ,當且僅當 在 中能推導 且 。
證明
(對分析樹高度作歸納)
先設 以一棵有限樹推導出 。對樹的高度作歸納:其首條規則要麼來自空產生式,此時 且 ;要麼來自原產生式 與相容序列 。把 寫成 ,其中 是第 個子節點的產出。若 是終結符,則 ,由相容性得 。若 是變元,子節點 的樹更矮,由歸納假設, 在 中推導 ,且 。因此在 中有 ,並且把 步合起來得 。在空的情形, 是原產生式,而 。
反過來,設根為 的原分析樹產出 ,且 。把 分成根規則右側各符號 的產出 ,其中終結符本身是一個符號的片段。令 、;這是每個片段前後唯一的 DFA 狀態,且 。對終結符 ,有 ,所以序列相容,根規則 存在。對變元 ,其子樹較矮,且其產出把 帶到 ,由歸納假設, 能推導 。把這些推導接到根規則上,便得 。若 ,則 且 ,可用明列的空規則。
證明透視
DFA 的各項假設用在哪裏
關鍵的一步,是讓文法選擇中間狀態,而讓字串去核對它們。構造為每條產生式列出每個狀態序列,等於一次猜遍所有可能的中間狀態;引理的兩個方向表明,只有 DFA 實際經過的序列才能得出完整的推導。
用到三項假設。 有限使規則表有限。 的確定性與全定義性使每個字串恰有一個狀態序列,所以反方向可以毫不含糊地選定根規則;若是 NFA,相容性應改為 ,引理則改為 。空規則要求 ,是 DFA 對空字串的行為進入證明之處:讀入 不會使它移動。
這個論證不能推廣到兩個文法。在邊界處,關於 DFA 的資訊是有限集合中的一對狀態;關於第二個文法的對應資訊,卻會是大小沒有上界、類似堆疊的物件。
定理 7.1.4
(對正則語言交集的封閉性)
設 為上下文無關文法, 為同一字母表上的 DFA。以 為起始變元的所構造文法,恰好產生 。特別地,上下文無關語言與正則語言的交集是上下文無關的。
證明
(選取接受的離開狀態)
僅有的規則是 (),所以 能推導 ,恰好當某個 使 能推導 。由引理,這恰好當 在 中推導 ,且對某個 有 ,亦即 且 。若 ,兩邊都是空集。證明使用的是有限推導樹。
概念視角結構
標註了自動機狀態的分析樹
所構造文法的分析樹,就是 的原分析樹,其中每個變元節點 帶有兩個標籤:DFA 在讀入該節點產出之前的狀態 ,以及讀完之後的狀態 。由左至右讀各葉子時,標籤首尾相接:一個片段的離開狀態就是下一個片段的進入狀態,而終結符葉 把 帶到 。所以交集文法並不是讓兩部機器並排運行,而是把 DFA 的軌跡記錄為分析樹上的標註。
例題:偶數層巢狀
例題 7.1.5
(含偶數個 a 的巢狀區塊)
取字母表 上的文法 ,它產生 ,其中非空規則巢狀套用 次。令雙狀態 DFA 從 開始並接受 ;每讀一個 便切換 ,讀 則保持狀態。它恰接受含偶數個 的字串。
對 ,以 表示另一狀態,非空產生式給出
空產生式給出 和 ;新起點只有規則 。例如,
依照引理,該文法恰產生 。空字串被包含:原文法和 DFA 都接受它,且 。
例題 7.1.6
(為何 ab 不被產生)
字串 屬於 ,因為 ,但 DFA 拒絕它。 的規則是 與 。要得到 ,必須用第一條,然後 。 僅有的規則是 ,而且不存在進入狀態為 、離開狀態為 的空規則。因此 不能推導 。
例題 7.1.7
(終結符在最後的位置,以及一個邊界情況)
設 有 ,產生 。令 DFA 每讀一個 便切換 ,讀 則保持不變,從 開始,只接受 。由相容性得,對所有 有 ;又因為 必須滿足 ,只有規則 與 。起始規則是 。於是
並且 。字串 不能被推導:它需要 ,但這不是規則,因為 令 DFA 停留在 。字串 也不能被推導:讀完 後變元又是 ,其唯一規則以 開頭。所產生的語言是 。
常見錯誤
(空規則的進入與離開狀態必須相同)
加入 的 看似無害,其實是錯的。在偶數層巢狀例子中,若加入 ,便會有 ,文法就會產生 ;它只有一個 ,被 DFA 拒絕。讀入空字串永遠不會令 DFA 移動,所以只有 是正確的。
限制與練習
構造假設 DFA 使用相同字母表;若輸入是 NFA,可先將它確定化。定理不證明兩個任意上下文無關語言的交集仍封閉,也不意味只憑有限規則構造就能有效解決所有涉及兩個文法的問題:它描述的是對指定輸入所作的有限轉換。
反例模式
同一想法不能用來交兩個上下文無關語言
斷言:若 與 都是上下文無關的,則 也是,方法是同一個三元組構造。取 ,由 、、 產生;又取 ,由 、、 產生。字串 屬於 恰好當 ,屬於 恰好當 ,所以 。依上下文無關語言的泵引理,這個語言不是上下文無關的;此標準結論在此不予證明。構造在這裏失效,是因為三元組以有限集合中的兩個狀態概括 DFA 的軌跡,而要概括第二個文法的堆疊,則需要沒有上界的資訊。定理要求兩個語言之一是正則的。
快速檢查
(在偶數層巢狀例題中,追蹤 DFA 讀取 的狀態,並解釋為何所構造起點能推導該字串。)
先追蹤 DFA 讀入四個 的狀態。
解答 · 答案
DFA 讀四個 時依次是 ,讀每個 時停留在 ,所以最後在接受狀態 。起點可推導該字串:,最後一步用 。
快速檢查
(若原文法有 ,為何只可在 時加入 ?)
讀入空字串時,DFA 的狀態會怎樣?
解答 · 答案
讀入 不會改變 DFA 的狀態,。若加入 的 , 就會推導出 ,而 ,與引理矛盾。在偶數層巢狀例子中,這會使 推導出 。
快速檢查
(若 ,新起點能推導甚麼?解釋為何這與交集一致。)
看看有哪些以 為左邊的規則。
解答 · 答案
不存在規則 ,所以 推導不出任何字串,所構造的語言為空。沒有接受狀態時 ,所以 ,兩者一致。