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

第4章

只想加入運算能力

我們在第 3 章研究有限自動機，這種虛構的機器剝除了真實電腦的複雜，並將它簡化到

最簡單的可能形式。我們深入探索了這些機器的行為，並也觀察了它們的用途；我們還

發現，儘管有不尋常的執行方法，非決定論有限自動機並不比更為傳統的決定論有限自

動機具備更多的功能。

就算加入像是非決定論和自由移動等奇特功能，我們也無法讓有限自動機更具威力。

而這雖然讓我們機器的計算能力有所提升，但卻也停滯在所有這些簡單機器共同的計算

能力。

如果不對機器運作方式做些激烈的改變，我們無法更加提升機器的能力。

所以這所有的機器實際上具有多大的威力？嗯，不多。它們僅限於非常特定的應用（接

受或拒絕整組字元），甚至在比這個還更小的範圍裡，依然很容易出現沒有機器能夠識

別的語言。

舉例來說，試著考慮設計這樣的有限狀態機：能夠讀取起始括號（左括號）和結束括號

（右括號）的字串，並且只有在這些括號前後

對稱

，才接受該字串，也就是如果結束括

號能與字串裡的前一個起始括號配對

1

。

一般來說，解決這個問題的策略是一次讀取 1 個字元，並在讀取字元的同時，將用來表

示目前巢狀層級的數值記錄下來：讀取起始括號增加巢狀層級，讀取結束括號減少巢狀

層級。只要巢狀層級為零，我們就知道截至目前已經讀取了對稱的括號（因為巢狀層級

1 這和接受僅包含數量相等的起始、結束括號的字串並不完全相同。字串 '()' 和 ')(' 都只包含一個起始、結

束括號，但只有 '()' 才對稱。

110

|

第 4 章

已經先上升再下降到完全相同的數量），而且如果我們試著將巢狀層級減少到零以下， ...