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

84

|

第 3 章

所以自由移動相當直覺就能實作，而且它們還提供了非決定論原本就已經提供的額外的

設計自由。

本章裡有若干未依照慣例的術語。有限自動機所讀取的字元通常稱為

符

號

（symbol），在狀態之間移動的規則稱為

轉移

（

transition

），構成機器

的諸多規則所成的集合稱為

轉移函數

（

transition function

，有時也稱為

NFA 的轉移關係 [

transition relation

]），而不是規則手冊。因為空字串的

數學符號是希臘字母

ε

（epsilon），能夠自由移動的 NFA 稱為 NFA-

ε

，而

自由移動本身通常稱為

ε

- 轉換

（

ε

-transitions

）。

正規運算式

我們已經看到非決定論和自由移動讓有限自動機更具表現能力，而不會干擾我們模擬它

們的能力。在這一節，我們將討論這些特性的重要實際應用：正規運算式的匹配。

正規運算式

（

regular expression

）提供了編寫文字

範式

（

pattern

）匹配字串的語言，以

下是一些正規運算式的範例：

•

hello

只和字串

'hello'

匹配

•

hello

|

goobye

能和字串

'hello'

和

'goodbye'

匹配

•

(hello)*

能和

'hello'

、

'hellohello'

、

'hellohellohello'

等字串以及空字串匹配

我們在本章一定是將正規運算式匹配整個字串，但在真實世界的正規運算

式實作物通常使用它們來匹配字串的某部分，如果我們想要指定應該匹配

的整個字串，就需要額外的語法。

舉例來說，我們會在 Ruby 裡將正規運算式 ...