深入理解運算原理｜從簡單的機器到無所不能的程式

116

|

第 4 章

決定論

接著要挑戰的是準確定義 PDA 成為決定論的意義。對於 DFA 來說，我們有『不矛盾』

的限制：因為衝突規則，所以機器的下一個移動不明確，就不應該有狀態。同樣的想法

也適用 DPDA，因此舉例來說，我們只能擁有一條適用在以下情況的規則：機器處於狀

態 2、下一個輸入字元是起始括號、堆疊頂端的字元為

b

。甚至撰寫不讀取任何輸入的

自由移動規則也無妨，只要相同狀態和堆疊頂端字元沒有任何其他規則即可，因為這會

造成是否該從輸入讀取字元的模糊空間。

DFA 也有『無遺漏』的限制（應該有一條針對每種可能情況的規則），但這樣的想法

對 DPDA 就變得難以處理，因為有大量可能合併的狀態、輸入字元、堆疊頂端字元。

很常見的是忽略這項限制，並允許 DPDA 為了完成它們的工作而僅指定相關的規則，

且若 DPDA 進入了無法適用其規則的情況，就會假設 DPDA 即將進入絕對的

停止狀態

（

stuck state

）。這就是當我們的對稱括號 DPDA 讀取了諸如

')'

或

'())'

之類的字串時

所發生的事，因為處於狀態 1 讀取結束括號的時候並沒有規則。

模擬物

現在我們已經處理了技術細節，接著讓我們建置決定論下推自動機的 Ruby 模擬物，以

便我們能與它互動。在模擬 DFA 和 NFA 時，我們已經完成最困難的工作了，因此這就

只需要做些微調就夠了。

堆疊是我們欠缺的最重要的東西，以下是實作

Stack

類別的方式之一：

class Stack < Struct.new(:contents)

def push(character) ...