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

80

|

第 3 章

一如我們所看到的

DFA

類別，只要一經要求，就能很方便的使用

NFADesign

物件自動造

出新的

NFA

實體，而不用手動建立它們：

class NFADesign < Struct.new(:start_state, :accept_states, :rulebook)

def accepts?(string)

to_nfa.tap { |nfa| nfa.read_string(string) }.accepting?

end

def to_nfa

NFA.new(Set[start_state], accept_states, rulebook)

end

end

這讓檢查相同 NFA 的不同字串變得更容易：

>> nfa_design = NFADesign.new(1, [4], rulebook)

=> #<struct NFADesign start_state=1, accept_states=[4], rulebook=…>

>> nfa_design.accepts?('bab')

=> true

>> nfa_design.accepts?('bbbbb')

=> true

>> nfa_design.accepts?('bbabb')

=> false

也就是說：藉著模擬它所有可能的執行情況，我們已經成功建置了罕見的非決定論機

器，雖然這只是簡單的實作物。非決定論是設計更複雜精巧的有限自動機的方便工具，

所以很幸運的是，NFA 不僅僅是理論，實際上的確可行而且有用。 ...