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

4.1

 決定性プッシュダウン・オートマトン

117

>>

dpda.current_configuration

=> #<struct PDAConfiguration state=2, stack=#<Stack (b)b$>>

>>

dpda.read_string('))()'); dpda.accepting?

=> true

>>

dpda.current_configuration

=> #<struct PDAConfiguration state=1, stack=#<Stack ($)>>

これまでと同様に、

DPDADesign

にラップしておくと、さまざまな文字列を簡単に好きなだけ

チェックできるようになります。

class DPDADesign < Struct.new(:start_state, :bottom_character,

:accept_states, :rulebook)

def accepts?(string)

to_dpda.tap { |dpda| dpda.read_string(

string) }.accepting?

end

def to_dpda

start_stack = Stack.new([bottom_character])

start_configuration = PDAConfiguration.new(start_state, start_stack)

DPDA.new(start_configuration, accept_states, ...