動機
上下文無關規則只改寫一個變元,而不顧其周圍環境,這就是堆疊已經夠用、同時 又無法企及的原因。要生成這樣的語言,文法必須能夠移動符號,並同時比較三個塊的個數。這裏研究的文法允許規則的左部是更長的串,同時加一個限制來控制推導:規則不得縮短句型。這一條限制有兩個重大後果。它使一個固定終結符字的推導中每個中間句型的長度都有上界,並且說明所生成的語言可以由一台永不離開輸入所佔帶區的機器識別。
我們證明一個完整的例子、長度引理、有界帶上接受問題的可判定性,以及從文法到有界帶機器的方向。反方向——從有界帶機器到文法——延後處理:這裏不予證明,下面也沒有任何陳述依賴它。我們同樣不對確定型與非確定型有界帶機器是否接受相同的語言作任何斷言。
定義
定義 4.1.1
(非收縮文法)
非收縮文法是 ,其中每條規則形如 ,, 至少含一個變元,且 。允許一個例外:可以有規則 ,條件是 不出現在任何右部。推導 、 與 的定義同上下文無關文法,一步是把 的某個出現替換為 。
若一個語言由某個非收縮文法生成,我們稱它為上下文有關語言。另有一種更嚴格的規則形狀 (),它給出同一類語言;這個等價性是標準定理,這裏不予證明,所以下面所有陳述都只涉及非收縮文法。
定義 4.1.2
(線性有界自動機)
線性有界自動機(LBA)是一台非確定型圖靈(Turing)機 ,其帶字母表 含兩個端點標記 。輸入為 時帶上是 ,讀寫頭從 出發。讀到 的轉移必須寫回 並右移;讀到 的轉移必須寫回 並左移;其他轉移都不得寫入端點標記。因此機器恰好使用存放輸入的 個單元,外加兩個端點標記。如果某條計算到達 ,則機器接受 。
輸入長度為 時,格局是一個三元組(狀態, 個內部單元的內容,讀寫頭在 個單元中的位置)。端點標記所在的單元永不改變,因此不需記錄。
定義 4.1.3
(長度不減的推導)
對非收縮文法,若推導 滿足 ,則稱它是單調的。
定理
定理 4.1.4
(長度引理與成員問題的可判定性)
設 是非收縮文法, 且 。若 ,則該推導從不使用 ,是單調的,且其中每個句型的長度至多為 。因此,通過探索長度至多為 的有限多個 上的串,可以判定 是否屬於 。
定理 4.1.5
( 的文法)
起始變元為 、規則為 ,,,,, 的文法是非收縮的,且恰好生成 。
定理 4.1.6
(有界帶機器的接受問題是可判定的)
設 是 LBA, 是長度為 的輸入。格局數至多為 ,並且 接受 當且僅當它有一條步數少於 的接受計算。因此存在一個算法,對作為數據給出的 LBA,判定 是否接受 。
定理 4.1.7
(從非收縮文法到 LBA)
對每個非收縮文法 ,存在 LBA 使 。
定理 4.1.8
(確定型標記算法)
存在一台確定型 LBA,它只使用 中的單元內容和端點標記,在 步內恰好接受 的字 。
證明思路
證明
(長度引理與可判定的成員問題)
長度引理。 推導中所用的規則把 替換為 ,且 ,唯一的例外是 。該例外需要有一個 的出現可供改寫;因為 從不出現在右部, 只出現在初始句型 中,所以這個例外只能是第一步,並產生 。對 ,例外從未使用,所以每一步都不縮短,推導是單調的,最後的句型 最長。關於可判定性:長度至多為 的 上的串的集合 是有限的。計算 中從 出發、通過應用結果仍在 內的規則所能到達的串的集合,反覆迭代直到不再有新的串加入;由前一部分, 當且僅當 在該集合中。
證明
(三塊文法的可靠性與完備性)
的文法。 每條規則都有 ,且每個左部都含變元,所以 是非收縮的; 出現在右部,但沒有規則 。對 的 :恰好應用 次 ,再應用 ,得到 。反覆使用 ,把每個 向左移過所有 ,得到 。然後 把第一個 變成 ,每個 變換下一個,類似地 之後用 自左至右把各個 轉換。
反向我們證明一個不變式。定義兩族串。第一族:,其中 含 個 與 個 。第二族:,其中 ,, 且 。我們斷言從 可達的每個句型都屬於這兩族之一。起始句型 屬於 的第一族。對 應用 得 ,屬於 的第一族;應用 得 ,屬於 、 的第二族。現在考慮對第二族句型 應用各條規則。規則 需要一對相鄰的大寫字母;大寫字母只出現在 中,所以它在 內起作用並保持各個個數。規則 需要小寫 緊跟 。 是開頭的一塊,其後的符號:若 是 的第一個符號,若 則是 的第一個符號。所以該規則只在 且 以 開頭時適用,產生 (),屬於 的第二族。規則 需要 緊接 之前:這只發生在 、 且 以 開頭時,給出 。規則 類似地需要 、 且 以 開頭,給出 。規則 需要 且 以 開頭,給出 。每種情形下個數條件都得以保持,因為一個大寫字母變成了對應的小寫字母。對第一族句型 起作用的規則只有兩條 -規則以及 內的 ;含 或 的規則不能適用,因為 把 與 隔開了。所以斷言成立。終結符字不含 、、,所以它屬於 的第二族,因而 ,該字為 的 。
證明透視
$a^n b^n c^n$ 文法的不變式在做甚麼
兩件事被一起保持:一個計數事實( 的個數、 或 的個數、 或 的個數相等)和一個次序事實(所有 在 之前, 在 之前,尚未確定的大寫字母拖在後面)。計數被保持,因為每條規則要麼每種字母類型各加一個,要麼只是給字母改標記。次序才是微妙之處:小寫字母只能緊接在已有的小寫字母之後生成( 接在 或 之後, 接在 或 之後),所以小寫字母由左至右增長。該不變式也解釋了那些死路—— 被困在小寫 之後:這樣的句型滿足計數事實,但永遠不可能變成終結符串。
證明
(以最短路徑判定有界帶上的接受)
有界帶上的接受問題。 格局由狀態( 種選擇)、 個內部單元( 種選擇)和讀寫頭位置( 種選擇)決定,由此得界 。把格局看作一個有限有向圖的頂點,每個可能的一步對應一條邊。接受意味著從初始頂點可以到達某個狀態為 的頂點。最短路徑經過的頂點互不相同,所以其邊數少於 。確定型算法探索該圖,例如作廣度優先搜尋,直到不再出現新頂點,若到達過接受狀態的頂點就回答「是」。重複格局之間的一段是可從接受路徑中刪去的環。非確定機器再次到達同一格局後仍可能選擇另一條出路;排除重複所依據的是最短路徑論證,而非所有未來選擇都必循環。
證明
(在填充帶上做反向推導)
從文法到 LBA。 固定 與輸入 ,。若 ,則恰好在 是規則時接受。設 ,以下所有逆規則選擇均排除例外 ,因為它不可能出現在非空字串的推導中。使用一個額外的帶符號 ,即不在 中的填充符號。不變式是:帶的內部始終具有形式 ,其中 是長度至多為 的句型。起初 。機器重複如下過程。首先檢查帶是否為 ;若是則接受。否則它猜測 的一條規則 和一個位置,並通過掃描驗證該處的單元含有 ( 的長度被 的某個常數所限制,所以這一檢查只需有限的記憶)。它把 替換為 ,把帶的其餘部分逐個符號地向左移動 個單元,並在右端寫下 個 。新的帶是 ,其中 是所選步驟的逆。所有操作都停留在 個內部單元之內。
正確性:若機器接受,則各輪之間帶內容給出句型 ,且 ,所以 。反之,若 且 ,由長度引理,存在一個所有句型長度至多為 的推導,所以機器可以逆向跟隨它,每輪選擇合適的規則和位置,最後在 處接受。該機器是非確定型的;這個證明並未產生確定型機器。
證明
(標記輪次的正確性與代價)
標記算法。 階段零用固定的有限個控制狀態掃描輸入一遍,除非輸入屬於 就拒絕;設三個個數為 。一輪從 開始。它跳過符號 ,若下一個符號是 就把它換成 ;然後向右越過各個 與 ,把第一個 換成 ;再越過各個 與 ,把第一個 換成 ;然後回到 。若期望的符號沒有找到(尋找 時掃描遇到 、 或 ,或尋找 時遇到 ),就拒絕。若第一個非 符號是 ,說明已沒有未標記的 :此時向右掃描,恰好在 之前只出現 與 時接受。經過 輪成功之後,未標記的個數分別是 、、。若 或 ,第 輪找不到所需符號而拒絕。若 輪都成功,則不再有 ,機器當且僅當不再有 和 時接受,即當且僅當 。每輪花費 步,至多有 輪。
反例模式
空字串例外不能隨意取消
斷言(錯誤):文法 是非收縮的,所以長度引理用字的長度來限制它的推導。事實上 是不允許的,因為 出現在右部。推導 的長度為 ,最後一步縮短了,所以長度引理對它不成立;對 ,若通過檢查長度至多為 的句型來判定成員問題,就會錯過長度為 的中間句型 。修正:引入新的起始變元 ,規則為 ,並令 。這樣 不出現在任何右部,每條規則都是非收縮的,語言不變。
概念視角算法
有界空間上的逆向推導即搜尋
該模擬並不生成字;它從輸入出發,逆向搜尋一個推導。每個帶內容是有限圖(有限字母表上長度為 的串)的一個節點,每次逆向應用規則是一條邊。長度引理保證圖是有限的,填充技巧使每個節點都放得進 個單元。接受就是從節點 到達唯一的節點 。
例題
例題 4.1.9
(推導 aabbcc)
取 :。各步依次使用 ,,對中間一對用 ,,, 與 。長度依次為 ,正如引理所要求的那樣不減。最後的句型每種字母各有兩個,與計數不變式相符。
例題 4.1.10
(一個無法完成的推導)
如前開始:。在第二個 處應用 得 ,再應用 得 。此時 之前是小寫 。沒有任何規則的左部以 結尾,而 要求 的左邊是大寫 ,所以沒有規則能作用於這個 。這個句型滿足計數不變式,但大寫字母出現在小寫 之後;它永遠不可能變成終結符串,這與證明中第二族要求小寫字母必須自左向右生成是一致的。
例題 4.1.11
(在六個單元的帶上逆向推導 aabbcc)
用填充符號 書寫帶。開始:。逆向 :。逆向 :。逆向 :。逆向 :。對中間一對逆向 :。對從第二個位置開始的塊 逆向 :塊 被換成 ,其餘部分左移兩個單元:。逆向 :四個單元 變成 ,帶為 。這就是 時的接受帶內容,所以機器接受。所有句型長度至多為 ,與長度引理的保證一致。
例題 4.1.12
(aabbcc 上的標記算法)
階段零確認形狀 之後,第一輪標記第一個 、第一個 與第一個 :。第二輪標記其餘的:。第三輪開始時,跳過 之後讀寫頭遇到 ,所以不再有 ;向右掃描直到 只發現 與 ,機器接受。對 ,第一輪得 ,第二輪標記 與 得 ,但隨後找不到未標記的 ,機器拒絕。
常見錯誤
常見錯誤
(空字串只能藉受保護的開始規則進入)
一個常見錯誤是說非收縮規則禁止語言含 。對 的例外(要求 不出現在右部)恰恰就是允許空字串的辦法。
常見錯誤
(CB 換成 BC 並非無關緊要的重排)
規則 是唯一移動大寫字母的規則,正是它使計數比較成為可能。它必須在 被轉換之前,把每個 都移到每個 之前;否則某個 可能被擱在小寫 的後面,如第二個例題所示。
常見錯誤
(不要把 LBA 的結果讀出超過已證明的內容)
說 LBA 可以「想用多少帶就用多少」是錯誤的。按這裏的定義,它恰好使用輸入單元與兩個端點標記,定義中沒有其他空間界。最後,不要從「文法到 LBA」的定理推出每個 LBA 語言都有文法,也不要推出已經比較了確定型與非確定型機器。這些陳述都在已證明的範圍之外。
總結
非收縮文法不能縮短句型,因而非空字串的每個推導都以該字的長度為界,成員問題隨之可判定。 的文法用一個明確的不變式來驗證。有界帶機器只有有限多個格局,所以其接受問題可判定。每個非收縮文法都可以由一台在填充過的帶上逆向運行推導的 LBA 來模擬。反方向延後處理,也不對確定性作任何斷言。
練習
快速檢查
(在第二個定理的文法中推導 ,並數出步數。)
解答 · 答案
(三步)。三次交換 得 (例如 )。然後 、、 得 (三步),再用 、、 得 (三步)。總計 步。
快速檢查
(在 上追蹤標記算法,並解釋它為甚麼拒絕。)
解答 · 答案
階段零接受形狀 。第一輪得 。第二輪標記剩下的 與 ,得 ,然後尋找未標記的 :跳過 後到達 ,於是拒絕。個數 不相等。
快速檢查
(一台 LBA 有 個狀態,帶字母表 的大小為 。對長度為 的輸入,用第三個定理中的公式給出格局數的界。)
解答 · 答案
界為 。任何接受計算都可取為少於 步。
快速檢查
(設 是變元集不相交、且沒有規則 的非收縮文法。構造 的非收縮文法並證明其正確性。)
解答 · 答案
取兩個文法的全部規則,再加一個新的起始變元 與規則 。這兩條新規則是非收縮的(長度相等,左部是變元),且 不出現在任何右部。由 推出的句型要麼是 ,要麼是由某個 推出的句型。由 推出的句型只含 的變元與終結符,而 ()的每條規則的左部含 的變元,所以不能適用。因此從 出發的推導恰是 或 的推導前面加一步,所得語言就是並集。