第四章：下推自动机

[murphywuwu]

• [x] 4.1确定性下推自动机
  • [x] 4.1.1 存储
  • [x] 4.1.2 规则
  • [x] 4.1.3 确定性
  • [x] 4.1.4 模拟
• [x] 4.2 非确定性下推自动机
  • [x] 4.2.1 模拟
  • [x] 4.2.2 不等价
• [x] 4.3 使用下推自动机进行分析
  • [x] 4.3.1 词法分析
  • [x] 4.3.2 语法分析
  • [x] 4.3.3 实践性
• [x] 4.4 有多少能力

[murphywuwu]

问题

假设要设计一台有限自动机，要求它能读取带有左右括号的字符串，并且只有字符串中的左右括号是平衡的，它才会接受。

• 解决这个问题的一般策略是一次读取一个字符串，同时跟踪一个表示当前嵌套级别的数字：读入一个左括号时增加嵌套级别，读入一个右括号时降低嵌套级别。只要嵌套级别到0了，就表示当前读到的这些括号已经都匹配上了(因为嵌套级别增加和减少的数量是一样的)，并且如果我们试图把嵌套级别降低到小于0的值，那就表明当前的右括号多了(如'())')，不管还有什么字符没有读取，字符串里的括号一定已经不平衡了。

作为一个良好的开始，我们可以为这个任务设计一台NFA。下面是拥有四个状态的NFA：

[murphywuwu]

一台拥有5个状态的NFA可以识别任意嵌套级别小于5的平衡字符串，而一台拥有10个，100个或者1000个状态的NFA，可以识别嵌套级别在机器硬限制以内的任意平衡字符串的NFA呢？结论是设计不出来：一台有限自动机的状态数总是有限的，因此任何机器能支持的嵌套级别也总是有限的，我们只要提供一个比它能处理的嵌套级别多一级的字符串，它就无法处理了。

根本问题是一台有限自动机只有固定的状态集合，因而其存储是有限的，因此没法跟踪任意数量的信息。

本质上大小固定的任务(比如对字符串'abc'进行匹配)，或者无需跟踪重复次数的任务(比如对正则表达式ab*c进行匹配)，都不受这个问题的影响，但在信息数目不可预知，需要在计算过程中存储并在之后重用的场景下，这个问题会让有限自动机无能为力

[murphywuwu]

确定性下推自动机

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

自带栈的有限状态机叫作下推自动机(PushDown Automaton, PDA)，如果这台机器的规则是确定性的，我们叫确定性下推自动机(Deterministic PushDown Automaton, DPDA)。

存储

为有限自动机增加存储的简单方式就是让它可以访问栈。对于栈的大小并没有内在的限制，因此原则上它可以根据需要存储数据。

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

能对栈进行访问带来了新的可能性，例如，很容易设计一台DPDA来识别括号组成的平衡字符串。

[murphywuwu]

给机器两个状态: 1和2，状态1作为接受状态

• 状态1作为机器的起始状态，此时栈为空
• 如果处于状态1, 读入一个左括号，就把字符b入栈，此时栈不为空, 因此转移到状态2
• 如果处于状态2，读入一个左括号，就把字符b入栈，此时栈不为空, 因此状态不变
• 如果处于状态2，读入一个右括号，就把字符b从栈中弹出，此时栈不为空, 因此状态不变
• 如果处于状态2且栈为空，就转移回状态1

栈为空时，意味着每一个左括号都已经匹配上了右括号，因此字符串一定是平衡的

[murphywuwu]

规则

我们PDA的规则分为5部分

• 机器的当前状态
• 输入字符
• 机器的下一状态
• 必须从栈中弹出的字符
• 栈顶字符弹出后需要推入栈中的字符序列

确定性

对于DFA来说，我们的约束是“不能存在冲突”：不能在任何状态上，由于冲突的规则而使机器下一次移动有二义性。这也适用于DPDA。

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

[murphywuwu]

我们可以通过跟踪一条信息来模拟确定性有限自动机，也就是跟踪DFA的当前状态，然后在每次输入读取字符时使用规则手册更新状态。但是关于下推自动机计算的每一步有两件重要的事情要知道：

• 它的当前状态是什么
• 栈的当前内容是什么

[murphywuwu]

对于一台有限自动机来说，遵守规则只是意味着从一个状态变成另一个状态，但一个PDA规则除了改变状态之外还要更新栈的内容。

[murphywuwu]

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

[murphywuwu]

在我们的状态机实验中，这是首次在模拟中引入了有可能的无限循环。只要有一个自由移动链，且它开始和结束状态相同，就会有循环。

#  无限循环：开始和结束状态相同
 DPDARulebook.new([
   PDARule.new(1, nil, 1, '$', ['$'])
 ]).follow_free_moves(PDAConfiguration.new(1, Stack.new(['$'])))

[murphywuwu]

rulebook = DPDARulebook.new([
  PDARule.new(1, 'a', 2, '$', ['a', '$']),
  PDARule.new(1, 'b', 2, '$', ['b', '$']),

  # b在栈顶
  # 读到b，就积累b
  PDARule.new(2, 'b', 2, 'b', ['b', 'b']),
  # 读到a，就弹出b
  PDARule.new(2, 'a', 2, 'b', []),

  # a在栈顶
  # 意味着机器已经看到a过剩了，因此任何额外从输入读取的a将会在栈中积累
  PDARule.new(2, 'a', 2, 'a', ['a', 'a']),
  # 而每读到一个b就会从栈中弹出一个a作为抵消
  PDARule.new(2, 'b', 2, 'a', []),

  PDARule.new(2, nil, 1, '$', ['$']),
])

dpda_design = DPDADesign.new(1, '$', [1], rulebook)

dpda_design.accepts?('ababab') # true
dpda_design.accepts?('bbbaaaab') # true
dpda_design.accepts?('baa') # false

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

[murphywuwu]

为了真正开发出栈的潜能，我们需解决一个更难的问题，存储结构化信息

识别回文字符串：随着一个字符一个字符地读取输入字符串，我们需要记住所看到的数据；一旦字符串读取过了一半，就要检查内存以确定之前看到的字符是否为当前呈现字符地逆序。

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

[murphywuwu]

非确定性下推自动机

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

没有确定性约束的下推自动机叫作非确定性下推自动机，如下所示

[murphywuwu]

使用下推自动机进行分析

下推自动机也有一个重要的实际应用：它们用来解析编程语言。

解析过程分成两个独立的阶段

• 词法分析 读取一个原始字符串然后把它转换成一个单词token序列。词法分析器使用称为词法的规则集合来决定什么样的字符应该产生什么样的单词。这个阶段处理杂乱的字符级别的的细节，比如变量名规则、注释和空格，它为下一阶段的处理准备好清楚的单词序列。

• 语法分析 读入一个单词序列并根据正在分析的语言语法判断它们是否代表一个有效的程序

[murphywuwu]

把字符串转成单词之后，难一些的问题就是确定这些单词是否表示一个语法有效的Simple程序了。我们不能使用正则表达式或者NFA---Simple的语法允许任意的括号嵌套，而我们已经知道有限自动机的能力不足以识别这样的语言。但是使用下推自动机是可以识别单词的有效序列的。

把文法规则转换成无需任何输入就能扩展栈顶的PDA规则。每一个文法规则描述了如何把一个符号扩展成由其他符号和单词组成的序列

[murphywuwu]

[murphywuwu]

这个执行过程的跟中向我们展示了机器在符号和单词规则之间的摇摆：符号规则不断地扩展栈顶字符，知道此符号被一个单词取代，然后单词规则再对栈(和输入)进行处理，直到遇到一个符号为止。只要输入字符串能够由文法规则生成，这样反复就能得到一个空栈

在每一步执行中PDA是怎么直到选择哪个规则呢？这是非确定性的力量：我们模拟的NPDA对所有可能的规则进行尝试，因此只要存在某种方式能得空栈，我们就能找到它

[murphywuwu]

while ( x < 5 x = x * }

从左到右依次验证，只要输入程序完全符合文法规则时，则当读取完输入程序时，栈为空，证明其为有效程序。