動機
前面的上下文無關一章已證明文法可由堆疊機器模擬,但泵引理顯式假設範式定理,機器到文法的反向構造也留待後續。本章補上兩項證明。前者簡化規則而保持終結字,後者用進入狀態、一個堆疊符號及退出狀態,概括可能很長的計算。
文法變元不一定表示可見的語法成分,也可以表達計算承諾。下文的 表示從狀態 開始,完成移除一個堆疊符號 的全部工作,並在狀態 結束。內部可以任意嵌套,但介面只有三個有限標籤。這解釋了為何有限文法足夠。
定義
定義 2.2.1
(可空變元、單位產生式與範式)
CFG 的變元若能推導空字串,稱為可空變元。 且兩者均為變元的規則是單位產生式。非空字串的 喬姆斯基(Chomsky)範式只允許 或 ,其中大寫為變元、小寫為終結符。若要保留空字串,可額外允許新開始變元的規則 ,但 不得出現在任何右側。
沿用前章 NPDA 約定:一次轉移讀 ,把堆疊頂符號替換為有限字串並改變狀態;接受要求輸入及堆疊同時為空,頂部寫在左邊。轉移表有限,不代表運行長度有界。
定義 2.2.2
(受保護移除)
讀取 的受保護移除從狀態 、堆疊 出發,在狀態 、堆疊 結束,並且直到最後一步才首次暴露下層後綴 。後綴的任何符號都未被檢查或改變。由於轉移只存取頂部,同一串步驟對任意後綴都成立。等價地,可在只有 的堆疊上檢驗,取首次變空時結束的運算,並記錄狀態與讀入字。
定理/命題
定理 2.2.3
(上下文無關範式)
每個 CFG 語言 都有範式文法生成 。若 ,以新開始變元的唯一例外空規則可保留整個語言。構造有限且有效,但不保證保持原來的分析樹或歧義。
定理 2.2.4
(從空堆疊 NPDA 構造文法)
每個按空堆疊接受的有限 NPDA 都有有限 CFG 生成 。結合前章反向模擬,CFG 與空堆疊 NPDA 描述完全相同的語言類。
證明思路
證明
(以可空刪除、單位消除與二元化得到範式)
先加入從不出現在右側的新開始變元及 。計算可空變元:先標記有空規則者,再反覆標記具有右側全為已標記變元的規則的左側。變元有限,過程必穩定。按標記階段歸納可證標記者確實可空;對空字串的分析樹歸納,則每個可空變元最終都被標記。
對每條規則,加入刪除任意若干可空變元出現位置所得的所有非空右側版本。刪除原空規則;當原開始變元可空時,僅保留 。原分析樹中剪去產生空字串的子樹,就得到新文法的非空字串分析樹。反向,在每個刪去位置插回該變元的一個空字串推導,就恢復原樹。每條右側只有有限個位置,所以新規則有限。這同時證明兩個語言包含方向。
再計算沿單位產生式的自反傳遞可達關係 。對每對可達變元,把每個非單位產生式 複製為 ,然後刪除所有單位產生式。原推導中的一串單位步驟及隨後的非單位步驟可縮成複製規則;反向沿有限單位路徑展開。由於 從不在右側,其他變元不能經單位路徑到達它,故例外空規則不會傳播到其他變元。
對長度至少二的右側中的終結符 ,用新變元 替代,並加入 。這只細分終結葉。最後把長度 的右側 改為
每條規則各用自己的新鏈變元。展開恰得原右側,收縮鏈又恢復原樹。其餘規則便是二變元或單終結符形式。去掉開始空規則得到非空語言;若無非空字串,開始變元沒有產生式就正確生成空語言。
證明
(三元變元描述受保護移除)
對 NPDA,為每個 引入變元 ,另設開始變元 ,對每個 加入 。考慮一次轉移:在 讀 ,把 替換為 ,進入 。若 ,加入 ,其中 表示空右側。若 ,對全部中間狀態 加入
時右側就是 。狀態、轉移及每次推入長度都有限,所以得到有限文法,並沒有給運行長度加上限制。
按分析樹歸納, 的一次推導先選最初轉移,再依次完成移除 的子推導。歸納假設給出各自受保護運算;在未改動的下層後綴之上依次執行,讀取各子字,便完成受保護移除 。直接彈出規則是一步的基礎情形。
反向對受保護移除的步數歸納。第一步若推入零個符號,就已首次暴露後綴,整段僅一步,直接彈出規則恰好生成讀入字。若推入 個符號,在首次依次暴露 、 直到 的時刻分段。每步高度至多下降一,且下層不能先於上層被存取,所以這些時刻都存在。每段比原運算短,是移除一個 的受保護運算,讀取連續輸入因子。由歸納得到相應三元變元推導,再選取記錄實際中間狀態的產生式,便生成全部輸入字。
接受運算從 首次變空必在最後,因為本模型空堆疊後無轉移,且接受要求輸入讀完。故它是從 到某個 的受保護移除。開始規則於是精確生成所有接受字,而非含糊地說「文法記住整個堆疊」。
證明透視
為甚麼運算會在首次暴露處分段
關鍵一步是反向的歸納,由三件事合起來支撐。轉移只查看堆疊頂部符號,所以在它上面的符號全部被移除之前,下層符號既不能被查看也不能被改變。堆疊高度每一步至多降低一,所以從 降到 的過程中,堆疊會依次首次到達各個後綴 。這些時刻把運算切成 個相連的片段,每個片段都是對某個 的受保護移除,且步數少於整個運算。最後,切分點上的狀態恰好就是產生式所需的標記 ,所以構造要遍歷中間狀態的每一種選擇:正確的產生式之所以存在,是因為它對所有選擇都已加入。若轉移能夠查看堆疊頂部以下的符號,切分點就不存在,三元組也就不能概括一個片段。
這裏的構造證明可以有效得到有限描述,並未無條件承諾相對於原始表示大小的多項式界。含許多可空出現位置的規則,可能產生許多刪除版本;較長的壓入字串也可能要求枚舉許多中間狀態組合。這不影響語言等價性的證明,卻影響把文法大小本身算作輸入時的複雜度分析。後續算法必須計入變換後的描述大小,或另行證明一種控制大小的規範化。存在性、有效構造與高效構造是不同的結論,不能悄悄把表示定理加強成效率定理。
例題
例題 2.2.5
(規範化匹配文法)
的非空語言可由 、、、 生成。第一分支是 ,第二分支是 ,歸納得恰好 、。若要保留空字串,加入開始變元 及 。 不在右側, 則在;空規則的特殊地位屬於 。
例題 2.2.6
(單位循環不產生新終結字)
取 、、。單位可達關係使三個變元都可達 ,因此每個都收到到 的規則。刪除單位產生式後,語言仍只有 。在 之間無限旅行本來就不是另一個終結字的有限推導;語言只量化有限推導。
例題 2.2.7
(一個堆疊符號與一個三元變元)
單狀態機器從 開始,讀 時把 換成 ,讀 時彈出 ,沒有其他轉移。唯一三元變元 給出 。字 對應 及高度 。 不接受,因為第一個 已清空而輸入未完,機器不能重啟。變元表示完整的一次移除,不是清空後又重新開始的任意運算段。
概念視角結構
變元作為計算介面
忘記嵌套工作的細節,只保留外部計算需要的進入狀態、被移除符號及下層首次可見時的退出狀態。雙向證明驗證了介面。只用狀態會丟失堆疊任務;每個完整字串各設一個變元又會無限。三元組正是有限而夠用的中間層。
常見錯誤
常見錯誤
(可空並不表示只能產生空字串)
可空只表示能產生空字串,不表示只能產生空字串。刪除可空出現位置是增加一個選擇,不是把它在所有規則使用中永久刪去。
常見錯誤
(二元化的鏈變元必須逐規則新設)
二元化時鏈變元應逐規則新設,否則不同規則可能混接,產生額外字。
常見錯誤
(受保護移除不能先檢查下層再恢復)
NPDA 構造是非確定性的;文法猜中間狀態沒有證明確定性堆疊機器也足夠。受保護移除不能先檢查下層後再恢復它;首次暴露條件正是遞歸組合正確的保障。
反例模式
只指定一個終止狀態並不足夠
斷言:對於空堆疊 NPDA,只需對某個選定的狀態 加入一條開始規則 。取 ,起始狀態 ,初始堆疊符號 ,且恰有兩條轉移:在 讀入 時把 替換為 並進入 ;在 讀入 時把 替換為 並留在 。單詞 和 都被接受,因為各自在輸入耗盡時清空了堆疊,而且沒有其他單詞被接受,所以 。構造給出 與 ,沒有其他右部非空的規則。只用 時,文法只生成 ;只用 時,只生成 。空堆疊接受並不指定最後的狀態,所以修正後的說法是對每個 都加入 。
總結
有限規則變換保持非空字串並產生二元分析樹,補全泵引理所需前提。三元變元概括受保護移除,為每個空堆疊 NPDA 產生 CFG,與前章一起完成語言等價。
練習
快速檢查
(對 、、,找可空變元並消除空及單位產生式。)
解答 · 答案
只有 可空, 不可空,故 也不可空。刪除 的空規則並在 中加入刪去 的版本 ,再去單位產生式,得 、、,語言為 ,與原來相同。
快速檢查
(為甚麼把 改為 、 安全,而任意跨規則共用鏈變元未必安全?)
解答 · 答案
兩分支共有起始 , 的兩個選擇恰好是原後綴,故安全。若把 、 改成 、、,就額外產生 、。逐規則使用新變元可阻止混接。
快速檢查
(用每個前綴及全字的 個數刻畫上述單狀態機器的語言。)
解答 · 答案
前綴 後高度為 。全字須有 比 多一;每個真前綴必須高度正,即 ,否則過早變空或無符號可彈。反向,這些條件保證每步合法,並在輸入結束時恰好清空,所以充要。
快速檢查
(對於單狀態 NPDA,轉移為 與 ,寫出由該構造給出的文法,並描述它的語言。)
解答 · 答案
只有一個三元變元 和開始規則 。讀入 的轉移壓入一個符號,故 ;讀入 的轉移彈出,故 。語言是 ,這正是機器所接受的語言:讀入 時保持 不變,在唯一的 上清空堆疊。