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

只想加入運算能力

|

123

def read_character(character)

self.current_configuration = next_configuration(character)

end

def read_string(string)

string.chars.each do |character|

read_character(character) unless stuck?

end

end

end

現在的 DPDA 就會停止，而非掛點：

>> dpda = DPDA.new(PDAConfiguration.new(1, Stack.new(['$'])), [1], rulebook)

=> #<struct DPDA …>

>> dpda.read_string('())'); dpda.current_configuration

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

>> dpda.accepting?

=> false

>> dpda.stuck?

=> true

>> dpda_design.accepts?('())')

=> false

非決定論下推自動機

雖然對稱括號機器確實需要堆疊來完成它的工作，但實際上它只將堆疊當作計數器來

用，它的規則只對『堆疊為空』和『堆疊不空』之間的區別有興趣。更複雜的 DPDA

會把一種以上的符號推入堆疊，並在它們執行運算時利用那些資訊。有個簡單的例子是 ...