アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

76

3

章 最も単純なコンピュータ

=> true

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

これで完成です。取り得る実行をすべてシミュレートすることで、非決定的な機械の実装が単純に

なりました。非決定性はもっ