返回介绍
文江博客 开发文档 计算的本质 - 深入剖析程序和计算机 文章详情

4.2 非确定性下推自动机

发布于 2023-05-18 19:12:04 字数 8812 浏览 0 评论 0 收藏 0

尽管处理平衡括号问题的机器确实需要栈来完成工作，但它其实只是将栈作为一个计数器，并且它的规则只区分“栈为空”和“栈不为空”。更复杂的DPDA 将会把一种以上的符号推入栈中，并在执行计算时使用这些信息。一个简单的例子是一台机器，它能识别包含相等数目的两种字符的字符串，比如a 和b：

我们的模拟表明它能完成工作：

>> rulebook = DPDARulebook.new([
    PDARule.new(1, 'a', 2, '$', ['a', '$']),
    PDARule.new(1, 'b', 2, '$', ['b', '$']),
    PDARule.new(2, 'a', 2, 'a', ['a', 'a']),
    PDARule.new(2, 'b', 2, 'b', ['b', 'b']),
    PDARule.new(2, 'a', 2, 'b', []),
    PDARule.new(2, 'b', 2, 'a', []),
    PDARule.new(2, nil, 1, '$', ['$'])
  ])
=> #<struct DPDARulebook rules=[...]>
>> dpda_design = DPDADesign.new(1, '$', [1], rulebook)
=> #<struct DPDADesign ...>
>> dpda_design.accepts?('ababab')
=> true
>> dpda_design.accepts?('bbbaaaab')
=> true
>> dpda_design.accepts?('baa')
=> false

这与平衡括号的机器类似，只是它的行为由栈顶字符控制。a 在栈顶意味着机器已经看到a 过剩了，因此任何额外从输入读取的a 将会在栈中累积，而每读到一个b 就会从栈中弹出一个a 作为抵销；反之，栈顶是b 时，就是b 在累积而用a 来抵销。

即使是这个DPDA 也没有利用栈的全部优点。在栈顶字符之下没有它感兴趣的任何历史数据，只有一些无意义的a 或b，因此我们可以只把一种字符推入栈（也就是说还是把它当作一个简单的计数器），并使用两个不同的状态区分“对过剩的a 计数”和“对过剩的b计数”，这样也能得到同样的结果：

为了真正开发出栈的潜能，我们需要一个更难的问题强迫我们存储结构化信息。经典的例子是识别回文字符串：随着一个字符一个字符地读取输入字符串，我们需要记住所看到的数据；一旦字符串读取过了一半，就要检查内存以确定之前看到的字符是否为当前呈现字符的逆序。下面这个DPDA 能够识别一个回文字符串，这个字符串由字符a 和b 组成，并 且在中间的位置有一个字符m（表示中间位置）：

这台机器从状态1 开始，不断从输入读取a 和b，然后把它们推入栈中。它读到m 的时候，会转移到状态2，在那里一直读取输入字符同时尝试把每一个字符都弹出栈。如果字符串后半部分的每一个字符都与栈中弹出的内容匹配，机器就停留在状态2 并最终碰到栈底的$，此时转移到状态3 并接受这个输入字符串。处于状态2 的时候，如果读入的任何字符与栈顶的字符不匹配，那就没有规则可以遵守，因此它将进入阻塞状态并拒绝这个字符串。

我们可以模拟这台DPDA 检查它的工作情况：

>> rulebook = DPDARulebook.new([
    PDARule.new(1, 'a', 1, '$', ['a', '$']),
    PDARule.new(1, 'a', 1, 'a', ['a', 'a']),
    PDARule.new(1, 'a', 1, 'b', ['a', 'b']),
    PDARule.new(1, 'b', 1, '$', ['b', '$']),
    PDARule.new(1, 'b', 1, 'a', ['b', 'a']),
    PDARule.new(1, 'b', 1, 'b', ['b', 'b']),
    PDARule.new(1, 'm', 2, '$', ['$']),
    PDARule.new(1, 'm', 2, 'a', ['a']),
    PDARule.new(1, 'm', 2, 'b', ['b']),
    PDARule.new(2, 'a', 2, 'a', []),
    PDARule.new(2, 'b', 2, 'b', []),
    PDARule.new(2, nil, 3, '$', ['$'])
  ])
=> #<struct DPDARulebook rules=[...]>
>> dpda_design = DPDADesign.new(1, '$', [3], rulebook)
=> #<struct DPDADesign ...>
>> dpda_design.accepts?('abmba')
=> true
>> dpda_design.accepts?('babbamabbab')
=> true
>> dpda_design.accepts?('abmb')
=> false
>> dpda_design.accepts?('baambaa')
=> false

这很好，但是输入字符串中间的m 是一种逃避。我们为什么不能设计一台机器，让它能识别回文字符串——aa、abba、babbaabbab 等——但无需在中间插入一个标记呢？

机器在到达字符串的中间位置时需要从状态1 转移到状态2，而没有标记的话，就没法知道什么时候做这样的状态转移。就像我们之前处理NFA 时看到的那样，这种“我怎么知道什么时候该……”的问题可以通过放松确定性约束并允许机器在任意时间都可以做重要的状态转移来解决，这样它就可能通过在正确的时间遵照正确的规则接受一个回文字符串。

不出所料的是，没有确定性约束的下推自动机叫作非确定性下推自动机（nondeterministic pushdown automaton）。下面是一台能识别由偶数个字母组成的回文字符串的非确定性下推自动机6：

6“ 偶数个字母”的约束能让机器保持简单：一个长度是 2n 的回文字符串可以通过先把 n 个字符推入栈然后再把n 个字符弹出栈来接受。为了识别任意的回文字符串，需要从状态1 到状态2 之间多一些规则。

除了状态1 到状态2 的规则，这和DPDA 的版本是一样的：在DPDA 中，它们从输入读取m，但这里是自由移动。这让NPDA 有机会在输入字符串的时候改变状态，而不再需要标记了。

4.2.1　模拟

一台非确定性机器要比一台确定性机器更难模拟，但我们在3.2.1 节中已经完成了NFA 中困难的部分，因此可以在处理NPDA 时重用同样的思想。我们需要一个NPDARulebook 来保存一个PDARule 的非确定性集合，它的实现也几乎和NFARulebook 完全一样：

require 'set'

class NPDARulebook < Struct.new(:rules)
  def next_configurations(configurations, character)
    configurations.flat_map { |config| follow_rules_for(config, character) }.to_set
  end

  def follow_rules_for(configuration, character)
    rules_for(configuration, character).map { |rule| rule.follow(configuration) }
  end

  def rules_for(configuration, character)
    rules.select { |rule| rule.applies_to?(configuration, character) }
  end
end

在3.2.1 节中，我们通过跟踪可能状态的集合来模拟一台NFA，这里会通过可能配置的集合来模拟一台NPDA。

我们的规则手册需要支持自由移动，这又一次几乎与NFARulebook 的实现一致：

class NPDARulebook
  def follow_free_moves(configurations)
    more_configurations = next_configurations(configurations, nil)
    if more_configurations.subset?(configurations)
      configurations
    else
      follow_free_moves(configurations + more_configurations)
    end
  end
end

在当前配置的集合之外，我们还需要一个NPDA 类来封装一个规则手册：

class NPDA < Struct.new(:current_configurations, :accept_states, :rulebook)
  def accepting?
    current_configurations.any? { |config| accept_states.include?(config.state) }
  end

  def read_character(character)
    self.current_configurations =
rulebook.next_configurations(current_configurations, character)
  end

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

  def current_configurations
    rulebook.follow_free_moves(super)
  end
end

这让我们可以随着每个字符的读入单步模拟出所有可能的配置：

>> rulebook = NPDARulebook.new([
    PDARule.new(1, 'a', 1, '$', ['a', '$']),
    PDARule.new(1, 'a', 1, 'a', ['a', 'a']),
    PDARule.new(1, 'a', 1, 'b', ['a', 'b']),
    PDARule.new(1, 'b', 1, '$', ['b', '$']),
    PDARule.new(1, 'b', 1, 'a', ['b', 'a']),
    PDARule.new(1, 'b', 1, 'b', ['b', 'b']),
    PDARule.new(1, nil, 2, '$', ['$']),
    PDARule.new(1, nil, 2, 'a', ['a']),
    PDARule.new(1, nil, 2, 'b', ['b']),
    PDARule.new(2, 'a', 2, 'a', []),
    PDARule.new(2, 'b', 2, 'b', []),
    PDARule.new(2, nil, 3, '$', ['$'])
  ])
=> #<struct NPDARulebook rules=[...]>
>> configuration = PDAConfiguration.new(1, Stack.new(['$']))
=> #<struct PDAConfiguration state=1, stack=#<Stack ($)>>
>> npda = NPDA.new(Set[configuration], [3], rulebook)
=> #<struct NPDA ...>
>> npda.accepting?
=> true
>> npda.current_configurations
=> #<Set: {
    #<struct PDAConfiguration state=1, stack=#<Stack ($)>>,
    #<struct PDAConfiguration state=2, stack=#<Stack ($)>>,
    #<struct PDAConfiguration state=3, stack=#<Stack ($)>>
  }>
>> npda.read_string('abb'); npda.accepting?
=> false
>> npda.current_configurations
=> #<Set: {
    #<struct PDAConfiguration state=1, stack=#<Stack (b)ba$>>,
    #<struct PDAConfiguration state=2, stack=#<Stack (a)$>>,
    #<struct PDAConfiguration state=2, stack=#<Stack (b)ba$>>
  }>
>> npda.read_character('a'); npda.accepting?
=> true
>> npda.current_configurations
=> #<Set: {
    #<struct PDAConfiguration state=1, stack=#<Stack (a)bba$>>,
    #<struct PDAConfiguration state=2, stack=#<Stack ($)>>,
    #<struct PDAConfiguration state=2, stack=#<Stack (a)bba$>>,
    #<struct PDAConfiguration state=3, stack=#<Stack ($)>>
  }>

最后用一个NPDADesign 类直接测试字符串：

class NPDADesign < Struct.new(:start_state, :bottom_character,
                :accept_states, :rulebook)
  def accepts?(string)
    to_npda.tap { |npda| npda.read_string(string) }.accepting?
  end

  def to_npda
    start_stack = Stack.new([bottom_character])
    start_configuration = PDAConfiguration.new(start_state, start_stack)
    NPDA.new(Set[start_configuration], accept_states, rulebook)
  end
end

现在可以检查一下NPDA 是否确实可以识别回文字符串：

>> npda_design = NPDADesign.new(1, '$', [3], rulebook)
=> #<struct NPDADesign ...>
>> npda_design.accepts?('abba')
=> true
>> npda_design.accepts?('babbaabbab')
=> true
>> npda_design.accepts?('abb')
=> false
>> npda_design.accepts?('baabaa')
=> false

看起来很好啊！非确定性明显已经给了我们确定性机器所不具备的识别语言的能力。

4.2.2　不等价

但是等一等：我们在3.4 节中看到，没有栈的非确定性机器在能力上与确定性机器是等价的。我们用Ruby 模拟的NFA 行为像是一台DFA（它们都是随着从输入读取字符在有限个“模拟状态”中转移），可以把任意一台NFA 转换成接受同样字符的DFA。那么非确定性真的能带给我们额外的能力，还是Ruby 模拟的NPDA 只是行为类似DPDA 呢？是否存在一个算法能把任意的非确定性下推自动机转换成确定性下推自动机呢？

答案是不存在。NFA 到DFA 的小把戏能成功，是因为我们可以使用一个DFA 状态表示多个可能的NFA 状态。为了模拟一台NFA，我们只需要跟踪现在它可能处于的状态，然后每次读取一个输入字符就选一个不同的可能状态集合，这样如果给它设定正确的规则，DFA 就可以轻松完成工作。

但这个小把戏不适用于PDA：我们不能有效地把多重NPDA 配置表示成一个DPDA 配置。并不奇怪，问题出在栈的上面。一个NPDA 模拟需要知道当前能出现在栈顶的所有字符，而且它必须能同时从几个模拟的栈弹出和推入。无法把所有可能的栈组合成一个栈，以便DPDA 仍能看到所有的栈顶字符并可以单独访问每个可能的栈。我们用Ruby 写一个程序做所有这些并不难，但是DPDA 没有足够的能力来处理。

所以不幸的是，我们的NPDA 模拟的行为并不像一台DPDA，也不存在NDPA 到DPDA的算法。无标记的回文问题就是这样一个例子，NPDA 能完成这个问题，但DPDA 不能，因此非确定性下推自动机确实比确定性的能力要强。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。
列表为空，暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文