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

114

|

第 4 章

狀態 接受與否？ 堆疊內容 剩下的輸入 動作

1 是 (()(()())) 讀取 (, 推入 b, 進入狀態 2

2 否 b ()(()())) 讀取 (, 推入 b

2 否 bb )(()())) 讀取 ), 推入 b

2 否 b (()())) 讀取 (, 推入 b

2 否 bb ()())) 讀取 (, 推入 b

2 否 bbb )())) 讀取 ), 提出 b

2 否 bb ())) 讀取 (, 推入 b

2 否 bbb ))) 讀取 ), 提出 b

2 否 bb )) 讀取 ), 提出 b

2 否 b ) 讀取 ), 提出 b

2 否 進入狀態 1

1 是 —

規則

DPDA 括號對稱背後的概念其實相當直覺，但在我們實際建置它之前，有一些瑣碎的技

術細節要先完成。首先，我們必須確定下推自動機的規則應該如何運作。這裡有幾項設

計的議題：

• 每條規則是否必須更改堆疊、讀取輸入或修改狀態，或者以上皆是？

• 是不是應該針對推入和提出而有兩種不同的規則？

• 當堆疊為空的時候，我們需要改變狀態的特殊規則嗎？

• 可以就像 NFA 裡的自由移動，也就是不讀取輸入就改變狀態嗎？

• 如果 DPDA 可以像這樣自行改變狀態，那麼『決定論』的意義為何？

選擇一種彈性大到足以支援我們所需一切的規則風格，我們就能回答這所有的問題。我

們將 PDA 規則分成 5 個部分：

• 機器的目前狀態

• 必須從輸入讀取的字元（非強制）

• 機器的下一個狀態

• 必須從堆疊提出的字元

• 提出頂端字元之後再推入堆疊的字元 ...