Question

为了解决存储问题，我们可以使用专门的原始空间扩展有限状态自动机，它负责在计算过程中存储数据。除状态提供的有限内部存储之外，这个空间给了机器一种外部存储（external memory）。就像我们将会发现的那样，拥有外部存储对于一台机器的计算能力关系重大。

4.1.1　存储

为有限自动机增加存储的简单方式就是让它可以访问栈，这是一个后进先出的数据结构，可以把字符推入和弹出。栈是简单而且有限制的数据结构——在任意时间都只有顶端的字符可以访问。为了查明栈下面位置的数据，我们只能丢弃顶层的字符，而一旦向栈内推入一串字符，我们就只能按相反的顺序把它们弹出——但它确实可以很好地解决有限存储的问题。对于栈的大小并没有内在的限制，因此原则上它可以根据需要存储数据。4

4当然，栈在现实世界中的任何实现都受限于计算机的RAM，或者硬盘上的空闲空间，或者宇宙中原子的数量，但是对于思维实验，我们将认为这些约束都不存在。

自带栈的有限状态机叫作下推自动机（PushDown Automaton，PDA），如果这台机器的规则是确定性的，我们就叫它确定性下推自动机（Deterministic PushDown Automaton，DPDA）。能对栈进行访问带来了新的可能性，例如，很容易设计一台DPDA 来识别括号组成的平衡字符串。下面是它的工作方式。

· 给机器两个状态：1 和 2，状态 1 作为接受状态。

· 状态 1 作为机器的起始状态，此时栈为空。

· 如果处于状态 1 并且读入一个左括号，就把某个字符——我们使用 b 表示“括号”——入栈，并转移到状态2。

· 如果处于状态 2 并且读入一个左括号，就把字符b 入栈。

· 如果处于状态 2 并且读入一个右括号，就把字符 b 从栈中弹出。

· 如果处于状态 2 且栈为空，就转移回状态1。

这台DPDA 使用栈的大小来记录到目前为止没有配上对的左括号数目。栈为空时，意味着每一个左括号都已经匹配上了右括号，因此字符串一定是平衡的。我们观察一下机器读入字符串'(()(()()))' 时栈的增长和缩减情况：

状态	是否接受	栈的内容	剩余输入	动作
1	是		(()(()()))	读入(，推入b，转移到状态2
2	否	b	()(()()))	读入(，推入b
2	否	bb	)(()()))	读入)，弹出b
2	否	b	(()()))	读入(，推入b
2	否	bb	()()))	读入(，推入b
2	否	bbb	)()))	读入)，弹出b
2	否	bb	()))	读入(，推入b
2	否	bbb	)))	读入)，弹出b
2	否	bb	))	读入)，弹出b
2	否	b	)	读入)，弹出b
2	否			转移到状态1
1	是			——

4.1.2　规则

括号平衡问题DPDA 背后的思想非常简单，但在我们实际构建它之前，需要弄清楚一些技术细节。首先，我们必须确定下推自动机的工作规则。这里有几个设计问题。

· 每个规则都要修改栈，或者读取输入，或者改变状态，还是三者都要做？

· 推入和弹出需要两种不同的规则吗？

· 栈为空时，我们是否需要一种特殊的规则改变状态呢？

· 就像 NFA中的自由移动那样，没有从输入读取就改变状态是否可以呢？

· 如果一台 DPDA 可以自发改变状态，那“确定性”是什么意思呢？

通过选择一种足够灵活、能满足所有要求的规则类型，我们可以回答全部问题。我们把一个PDA 规则分成5 部分：

· 机器的当前状态；

· 必须从输入读取的字符（可选）；

· 机器的下一个状态；

· 必须从栈中弹出的字符；

· 栈顶字符弹出后需要推入栈中的字符序列。

前三部分很熟悉，它们来自DFA 和NFA 的规则。如果一个规则不想让机器改变状态，它可以让下一个状态与当前状态一样；如果它不想读取任何输入（也就是自由移动），则可以忽略输入字符，只要这不让机器变成非确定性的就可以（参见4.1.3 节）。

其他两部分——要弹出的字符和要推入的字符序列——是PDA 特有的。假定一台PDA 总是要弹出栈顶字符，然后向栈中推入其他字符。每一个规则声明它想要弹出哪个字符，然后这个规则只会在这个字符处于栈顶位置时才会应用；如果这个规则想让那个字符留在栈中而不弹出，它可以把这个字符包含在后来要推入栈中的字符序列当中。

这个五部分的规则格式没有说明栈为空时如何写规则，但我们可以通过选择一个特殊符号标记栈底位置来解决——流行的选择是$——然后每当想要检测栈是否为空时，检查这个符号就可以了。使用这个约定时，最重要的是永远不要让栈真的变空，因为在栈顶为空时没有规则可以应用。机器开始的时候这个特殊的栈底符号应该已经在栈中，任何规则在把这个符号弹出之后必须再次把它推入。

很容易用这种格式重写平衡括号的DPDA 规则：

· 处于状态 1 而且读入左括号时，弹出字符$，推入字符 b$，然后转移到状态 2；

· 处于状态 2 而且读入左括号时，弹出字符b，推入字符 bb，然后保持在状态 2；

· 处于状态 2 而且读入右括号时，弹出字符b，不推入任何字符，然后保持在状态 2；

· 处于状态 2（没有读入任何字符）时，弹出字符 $，推入字符 $，然后转移到状态 1。

我们可以用这个机器的图来展示这些规则。DPDA 图看起来与NFA 图很像，但DPDA 图的每个箭头不仅要标记它从输入读取的字符，还要标记这个规则需要弹出和推入的字符。如果我们使用符号a;b/cd 来标记一个规则，它表明从输入读取a，从栈中弹出b，然后向栈中推入cd，这个机器看起来像是这样：

4.1.3　确定性

下一个难题就是为PDA 准确地定义确定性的含义。对于DFA 来说，我们的约束是“不能存在冲突”：不能在任何状态上，由于冲突的规则而使机器的下一次移动有二义性。这也适用于DPDA，例如，在机器处于状态2、下一个输入字符是左括号并且栈顶是b 的时候，我们只能应用一个规则。甚至写一个不读取任何输入的自由移动规则都是可以的，只要对于同样的状态和同样的栈顶字符没有其他规则可用就可以，因为这样在确定一个字符是否应该从输入读取的时候会产生二义性。

DFA 还有“不能有遗漏”的约束（每一个可能的情况都应该有一个规则），但是因为状态、输入字符和栈顶字符有大量可能的组合，所以这对于DPDA 来说很难处理。通常只是忽略这个约束并允许DPDA 只定义完成工作所需的规则，并且假定一台DPDA 在没有规则可用时将进入停滞状态。我们的平衡括号DPDA 在读取')'或'())' 这样的字符串时会进入这种情况，因为处于状态1 且读入一个右括号时没有规则可用。

4.1.4　模拟

既然处理完了技术细节，让我们构建一个确定性下推自动机的Ruby 模拟吧，这样就可以与它交互了。在模拟DFA 和NFA 的时候我们已经完成了大部分困难的工作，因此这次只需要微调。

我们缺少的最重要的东西是栈。下面是一种实现栈类的方式：

class Stack < Struct.new(:contents)
  def push(character)
    Stack.new([character] + contents)
  end

  def pop
    Stack.new(contents.drop(1))
  end

  def top
    contents.first
  end

  def inspect
    "#<Stack (#{top})#{contents.drop(1).join}>"
  end
end

一个Stack 对象把它的内容存储在一个数组内并把简单的#push 和#pop 操作暴露出来以支持字符的推入和弹出，另外还有一个#top 操作可以读取栈顶的字符：

>> stack = Stack.new(['a', 'b', 'c', 'd', 'e'])
=> #<Stack (a)bcde>
>> stack.top
=> "a"
>> stack.pop.pop.top
=> "c"
>> stack.push('x').push('y').top
=> "y"
>> stack.push('x').push('y').pop.top
=> "x"

这仅仅是一个纯功能性的栈。#push 和#pop 方法是非破坏性的：它们每一个都返回一个新的栈实例而不是修改已有的栈。每次都创建一个新的栈对象比通常拥有破坏性#push 和#pop 方法操作的栈（如果我们想这样，可以直接使用Array）效率要低，但是使用起来要更容易，因为在多处使用一个Stack对象的时候，我们不必担心对其进行修改的后果。

第3 章里，我们可以通过只跟踪一条信息来模拟确定性有限自动机，也就是跟踪DFA 的当前状态，然后在每次从输入读取字符时使用规则手册更新该状态。但是关于下推自动机计算的每一步有两件重要的事情要知道：它的当前状态是什么，栈的当前内容是什么。如果我们使用名词配置表示一个状态和一个栈的组合，则在下推自动机读取输入字符时，我们可以说它从一个配置转移到了另一个配置，这比总是需要分别提到状态和栈要容易。从这个角度看的话，一台DPDA 只会有一个当前配置，并且每次读取一个字符时规则手册都会告诉我们如何把当前配置转换成下一个配置。

下面是用来存储PDA 配置（一个状态和一个栈）的一PDAConfiguration 类，以及一个用来表示一台PDA 的规则手册中的一个规则的PDARule 类：5

5因为它们的实现并没有做任何确定性的假设，所以这些类的名字以PDA 开头，而不是以DPDA 开头，这样它们在模拟非确定性PDA 时也工作得很好。

class PDAConfiguration < Struct.new(:state, :stack)
end

class PDARule < Struct.new(:state, :character, :next_state,
               :pop_character, :push_characters)

  def applies_to?(configuration, character)
    self.state == configuration.state &&
      self.pop_character == configuration.stack.top &&
      self.character == character
  end
end

只有在机器状态、栈顶字符和下一个输入的字符都为期望值的时候才能应用规则：

>> rule = PDARule.new(1, '(', 2, '$', ['b', '$'])
=> #<struct PDARule
    state=1,
    character="(",
    next_state=2,
    pop_character="$",
    push_characters=["b", "$"]
>
>> configuration = PDAConfiguration.new(1, Stack.new(['$']))
=> #<struct PDAConfiguration state=1, stack=#<Stack ($)>>
>> rule.applies_to?(configuration, '(')
=> true

对一台有限自动机来说，遵守规则只是意味着从一个状态变成另一个状态，但一个PDA规则除了改变状态之外还会更新栈的内容，因此PDARule#follow 需要接受机器的当前配置作为参数然后返回下一个配置：

class PDARule
  def follow(configuration)
    PDAConfiguration.new(next_state, next_stack(configuration))
  end

  def next_stack(configuration)
    popped_stack = configuration.stack.pop

    push_characters.reverse.
      inject(popped_stack) { |stack, character| stack.push(character) }
  end
end

如果我们把一些字符先推入栈中然后再把它们弹出，则它们出来时的顺序会与之前的顺序相反：

> stack = Stack.new(['$']).push('x').push('y').push('z')
=> #<Stack (z)yx$>
> stack.top
=> "z"
> stack = stack.pop; stack.top
=> "y"
> stack = stack.pop; stack.top
=> "x"

PDARule#next_stack 通过在把字符推入栈之前先把push_characters反转的办法解决这个问题。例如，push_characters 的最后一个字符实际上是推入栈中的第一个字符，这样再次弹出的时候它就又是最后一个字符了。这只是为了方便我们把规则的push_characters 按照字符序列读取（以“弹出的顺序”），这些字符序列在规则应用之后会出现在栈顶，这样我们就不用关心它们到达栈顶的机制了。

因此，如果把一个PDARule 应用到一个PDAConfiguration 上，就可以通过这个规则找出接下来的状态和栈是什么样的：

>> rule.follow(configuration)
=> #<struct PDAConfiguration state=2, stack=#<Stack (b)$>>

这足以实现DPDA 的规则手册了。这个实现与3.1.4 节的DFARulebook类似：

class DPDARulebook < Struct.new(:rules)
  def next_configuration(configuration, character)
    rule_for(configuration, character).follow(configuration)
  end

  def rule_for(configuration, character)
    rules.detect { |rule| rule.applies_to?(configuration, character) }
  end
end

现在我们可以为平衡括号DPDA 汇编一个规则手册了，然后尝试手工单步调试一些配置和输入字符：

>> rulebook = DPDARulebook.new([
    PDARule.new(1, '(', 2, '$', ['b', '$']),
    PDARule.new(2, '(', 2, 'b', ['b', 'b']),
    PDARule.new(2, ')', 2, 'b', []),
    PDARule.new(2, nil, 1, '$', ['$'])
  ])
=> #<struct DPDARulebook rules=[...]>
>> configuration = rulebook.next_configuration(configuration, '(')
=> #<struct PDAConfiguration state=2, stack=#<Stack (b)$>>
>> configuration = rulebook.next_configuration(configuration, '(')
=> #<struct PDAConfiguration state=2, stack=#<Stack (b)b$>>
>> configuration = rulebook.next_configuration(configuration, ')')
=> #<struct PDAConfiguration state=2, stack=#<Stack (b)$>>

为了代替手工操作，我们可以使用规则手册构建一个DPDA 对象，它会在从输入读取字符的同时跟踪机器的当前配置：

class DPDA < Struct.new(:current_configuration, :accept_states, :rulebook)
  def accepting?
    accept_states.include?(current_configuration.state)
  end

  def read_character(character)
    self.current_configuration =
      rulebook.next_configuration(current_configuration, character)
  end

  def read_string(string)
    string.chars.each do |character|
      read_character(character)
    end
  end
end

这样我们可以创建一个DPDA，提供输入，然后看它是否能够接受这些输入：

>> dpda = DPDA.new(PDAConfiguration.new(1, Stack.new(['$'])), [1], rulebook)
=> #<struct DPDA ...>
>> dpda.accepting?
=> true
>> dpda.read_string('(()'); dpda.accepting?
=> false
>> dpda.current_configuration
=> #<struct PDAConfiguration state=2, stack=#<Stack (b)$>>

到目前为止一切都很好，但我们正在使用的规则手册中包含一个自由移动，因此模拟需要支持自由移动以便正确工作。让我们增加一个DPDARulebook 的辅助方法以处理自由移动，这与NFARulebook 中的类似（参见3.2.2 节）：

class DPDARulebook
  def applies_to?(configuration, character)
    !rule_for(configuration, character).nil?
  end

  def follow_free_moves(configuration)
    if applies_to?(configuration, nil)
      follow_free_moves(next_configuration(configuration, nil))
    else
      configuration
    end
  end
end

DPDARulebook#follow_free_moves 将不断地反复执行能应用到当前配置的任何自由移动，直到没有自由移动的时候才会停止：

>> configuration = PDAConfiguration.new(2, Stack.new(['$']))
=> #<struct PDAConfiguration state=2, stack=#<Stack ($)>>
>> rulebook.follow_free_moves(configuration)
=> #<struct PDAConfiguration state=1, stack=#<Stack ($)>>

在我们的状态机实验中，这是首次在模拟中引入了有可能的无限循环。只要有一个自由移动链，且它的开始和结束状态相同，就会有循环。最简单的例子是存在一个根本不改变配置的自由移动：

> DPDARulebook.new([PDARule.new(1, nil, 1, '$', ['$'])]).
follow_free_moves(PDAConfiguration.new(1, Stack.new(['$'])))
SystemStackError: stack level too deep

这些无限循环毫无用处，因此我们在设计下推自动机的时候要注意避免它们。

我们还需要封装DPDA#current_configuration 的默认实现，以便利用规则手册对自由移动的支持：

class DPDA
   def current_configuration
    rulebook.follow_free_moves(super)
  end
end

现在我们有了可以启动、接受字符输入并且检查是否接受输入的DPDA 模拟了：

>> dpda = DPDA.new(PDAConfiguration.new(1, Stack.new(['$'])), [1], rulebook)
=> #<struct DPDA ...>
>> dpda.read_string('(()('); dpda.accepting?
=> false
>> 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, rulebook)
  end
end

不出所料，我们的DPDA 可以识别任意嵌套深度的平衡括号组成的复杂字符串：

>> dpda_design = DPDADesign.new(1, '$', [1], rulebook)
=> #<struct DPDADesign ...>
>> dpda_design.accepts?('(((((((((())))))))))')
=> true
>> dpda_design.accepts?('()(())((()))(()(()))')
=> true
>> dpda_design.accepts?('(()(()(()()(()()))()')
=> false

还有最后一个细节要注意。输入后DPDA 处于有效状态时，我们的模拟运行得很完美，但在机器卡住的时候它就会出问题了：

>> dpda_design.accepts?('())')
NoMethodError: undefined method `follow' for nil:NilClass

之所以会发生这种情况，是因为DPDARulebook#next_configuration假设它总能找到可用的规则，因此在没有规则可用的时候我们不应该调用它。修改DPDA#read_character 检查可用规则，如果没有可用规则，就把DPDA 置于一个无法转移出去的阻塞状态，这样我们就解决了这个问题：

class PDAConfiguration
  STUCK_STATE = Object.new

  def stuck
    PDAConfiguration.new(STUCK_STATE, stack)
  end

  def stuck?
    state == STUCK_STATE
  end
end

class DPDA
  def next_configuration(character)
    if rulebook.applies_to?(current_configuration, character)
      rulebook.next_configuration(current_configuration, character)
    else
      current_configuration.stuck
    end
  end

  def stuck?
    current_configuration.stuck?
  end

  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