我們即將失去的那份安心
把思緒拉回兩階之前，回到你跑子集構造、證明了每台 NFA 都能重建成一台 DFA的那時候。那個寓意令人安心：非確定性——那招「把自己複製、同時嘗試每條路」的把戲——在「能力」上沒替你買到任何東西，只買到了簡潔。一台 NFA 也許更小、更好畫，但一台確定型機器永遠能辨識同一個語言，即使它得用上多達 2^n 個狀態。猜測是一種方便，從不是一種必需。
我們很容易以為：一旦栓上一座堆疊，同樣的事也會延續下去。本階前幾篇導覽已經建起了完整的下推自動機：一個有限的控制單元，加上一座當作無界後進先出記憶體的堆疊，並在一套獨立的堆疊字母表上做推入與彈出。你也許想：確定化後的版本想必一樣強吧？這篇導覽存在的目的，就是誠實地告訴你：並不是。確定型下推自動機所辨識的語言類別，嚴格地小於非確定型的。那個來自有限自動機的直覺破裂了，而且這破裂不是技術細節——它正是剖析器之所以被造成那個樣子的原因。
什麼使一台 PDA 成為確定型
首先我們得把規則釘死。一台非確定型 PDA 在任何瞬間，都可以看著它目前的狀態、下一個輸入符號、以及堆疊頂端的符號，然後面對「好幾個」合法的動作——而且關鍵是，它還可以做一次 epsilon 動作（一個完全不讀輸入、只重排堆疊的動作）。只要「某一條」選擇序列通往接受，這台機器就贏。一台確定型下推自動機把這份「選擇」整個拆掉：從任何一個組態出發，它至多只有一個動作可做。沒有岔路、沒有分身、沒有幸運的一猜。
要把「至多一個動作」講精確，得格外當心那些 epsilon 動作。確定性條件有兩部分。其一，對任何狀態 q、輸入符號 a、堆疊頂端符號 X，轉移 delta(q, a, X) 至多只能提供一個選項。其二——微妙的那部分——若存在一個 epsilon 動作 delta(q, epsilon, X)，那麼對同一個狀態與堆疊頂端，就「不可」存在任何讀輸入的動作 delta(q, a, X)。否則機器就能在「讀」與「不讀」之間挑選，而那個挑選恰恰就是我們正在禁止的那份非確定性。把兩者都釘死，機器的整段執行就成了一條單一、被逼定的瞬時描述之線。
那個非猜不可的語言
抽象的東西，只有在你遇上一個能擊敗它的字串時才會說服人，所以這裡有個經典的見證者。考慮 {a, b} 上「偶數長度回文」的語言——正著讀與倒著讀一模一樣、且恰好對半切的字串，像那個形式集合 { w 後接 w 的逆序 }。一台非確定型 PDA 能輕鬆辨識它。當它讀前半段時，把每個符號推入堆疊。在「某個」點上，它必須決定「中點就在這裡」，停止推入，改以彈出去匹配後半段。從中點起，每個輸入符號都必須等於從頂端彈出的符號，而若堆疊恰好在輸入結束時清空，就接受。
注意那個承載重量的詞：「某個點上」。機器沒有任何標記告訴它中間在哪——字串 www...w 只是一直來，中心要事後回看才看得見。非確定型 PDA 靠猜中點再驗證來閃過這點：它在每個位置上概念性地複製自己，其中一個分身猜「中間就在這裡」。猜對的那個分身一路跑到乾淨的接受；猜錯的就乾脆死掉。這正是你在 NFA 那裡見過的、有紀律而非隨機的猜測——一種數學上的「試遍每條分支」，不是擲銅板。但這裡它在做一件 NFA 的猜測從不需要做的事：在無界的記憶體裡定位一道看不見的邊界。
現在試著把那個猜測拿掉。一台確定型 PDA 在每一步都必須走它那唯一被逼定的動作、無力分岔——所以它只能根據「至今讀到了什麼」去「承諾」一個中點，而字串其餘部分仍未見。可是回文的中心無法在本地被偵測：aabaa 與 aabbaa 與 aabXbaa 只在機器尚未抵達的某個位置上才分道揚鑣。任何單一的、被承諾的猜測都可能出錯，而確定型機器拿不到第二條分支可退守。這就是為何一台 PDA 的非確定性並非免費的核心：那個猜測在做真正的工作，是確定性複製不出來的。
那條界線落在哪裡
於是確定型機器切出了它自己那塊較小的類別。一台 DPDA（以最終狀態接受）能辨識的語言，恰好就是確定型上下文無關語言，即 DCFL。它們嚴格地坐落在上下文無關語言之內：每個 DCFL 都是上下文無關的，但——如回文所示——有些上下文無關語言不是確定型的。回想本階稍早的全景：完整的 PDA 與上下文無關文法是同一枚硬幣的兩面，那個PDA–CFG 等價證明了彼此可互相轉換。而 DCFL 是那塊 CFG 形狀領土裡一個真正的子區域。
CONTEXT-FREE LANGUAGES (= what full PDAs recognise)
+---------------------------------------------------------------+
| |
| DETERMINISTIC CFLs (= what DPDAs recognise) |
| +-------------------------------------------+ |
| | a^n b^n balanced ( ) | |
| | a^n b^m (n != m) | |
| | most programming-language syntax | |
| +-------------------------------------------+ |
| |
| NOT deterministic (need the guess): |
| { w w-reversed } even palindromes |
| a^n b^n UNION a^n b^2n |
+---------------------------------------------------------------+
regular languages (\subset) DCFL (\subset, strict) CFL
contrast: for FINITE automata, DFA-power = NFA-power (no strict gap)DCFL 界線裡面有什麼？很多，而且很有用。前一篇導覽裡的招牌例子 a^n b^n 就是確定型的：每個 a 都說「推入」，而第一個 b 就把機器永久切換進「彈出模式」——關於邊界在哪根本不必猜，因為字母的改變宣告了它。成對括號是確定型的。n 不等於 m 的 a^n b^m 也是。這些恰恰是那種「結構會本地地、毫不含糊地告訴機器下一步該做什麼」的語言——而正是那個性質，讓一台確定型堆疊機器能搞定它們。
為何每個真實剖析器都在意
這不是抽象的分類學——它是你的編譯器之所以快的工程理由。一個一般的上下文無關文法，可以用一台Earley 式剖析器在大約 O(n^3) 的時間內剖析，因為它實際上必須讓非確定型 PDA 的眾多猜測平行地活著。確定性才是讓剖析跑出 O(n) 的東西——單一次線性掃過，毫無回溯。所以編譯器作者希望他們語言的文法落在 DCFL 之內，那裡一台確定型機器就夠用了。
那份渴望，正是真實剖析器之所以限制它們所接受文法的原因。那些熟悉的剖析器類別——LL(k)，由左到右閱讀、帶固定 k 個符號的前瞻；以及 LR(k)，更強大的由下而上家族——恰恰就是確定型策略。一台 LR(k) 剖析器，在引擎蓋底下就是一台確定型下推自動機；而 LR(1) 文法這個類別所生成的，恰好就是確定型上下文無關語言。當一個剖析器產生器抱怨「移入／歸約衝突」時，它是在用工具的語言告訴你：在某個組態上它面對兩個動作、無法確定地選擇——你的文法已游離到 DCFL 之外，你必須重構它。
最後一個誠實的加碼，因為它顯示確定性真的改變了數學本身、而不只是速度。完整的上下文無關語言對補集「不」封閉——把裡外翻轉，可能就離開了 CFL 的世界。但確定型 CFL「對補集封閉」：因為一台 DPDA 的執行是一條單一、被逼定的線，你（小心處理那些 epsilon 動作與死路之後）可以把「接受」與「不接受」的命運對調，仍然得到一台有效的 DPDA。這呼應了一台 DFA 只要翻轉它的接受狀態就能輕易取補集，而這個性質是那些狂野、愛猜的 PDA 根本沒有的。確定性不只讓這些語言剖析得更快——它讓它們更循規蹈矩。