Question

第3 章探讨了有限自动机，这是一种假想的机器，它去掉了真实计算机的复杂性并把其规约成了最简单的形式。我们详细考察了这些机器的行为并了解了它们的用处，而且还发现，非确定性有限自动机虽然有一些奇特的执行方法，但计算能力并不比确定性有限自动机强。

我们没法通过为有限自动机增加非确定性和自由移动这种奇特的特性来提高它的计算能力。这个事实表明，我们已经停留在这些简单机器的计算水平上无法前进了。而且如果不从根本上改变机器的工作方式，将无法脱离这种停滞不前的境地。那么，所有这些机器到底有多强的能力呢？好吧，没有多少能力。它们被限制在非常有限的应用上（只能接受或者拒绝字符序列），而且即使在这么小的范围内，仍然很容易碰到机器无法识别的 语言。

举个例子，假设要设计一台有限自动机，要求它能读取带有左右括号的字符串，并且只有字符串中的左右括号是平衡的（即每一个右括号都能在字符串中找到与其匹配的左括号），它才会接受。1

1这与接受仅包含同样数量的左右括号的字符串完全不同。字符串'()' 和')(' 都有一个左括号和一个右括号，但只有'()' 是平衡的。

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

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

每个状态都对应一个嵌套级别，读取一个左括号或者一个右括号会分别让机器转移到与更高或者更低级别对应的状态，“没有嵌套”对应的就是接受状态。我们已经实现了用Ruby模拟这台NFA 所需要的一切，因此来运行一下：

>> rulebook = NFARulebook.new([
    FARule.new(0, '(', 1), FARule.new(1, ')', 0),
    FARule.new(1, '(', 2), FARule.new(2, ')', 1),
    FARule.new(2, '(', 3), FARule.new(3, ')', 2)
  ])
=> #<struct NFARulebook rules=[...]>
>> nfa_design = NFADesign.new(0, [0], rulebook)
=> #<struct NFADesign start_state=0, accept_states=[0], rulebook=...>

对于某些输入，我们的NFA 工作得很好。它能确定'(()' 和'())' 的括号不平衡，而'(())' 的括号是平衡的，它甚至能识别'(()(()()))' 这种更为复杂的平衡字符串：

>> nfa_design.accepts?('(()')
=> false
>> nfa_design.accepts?('())')
=> false
>> nfa_design.accepts?('(())')
=> true
>> nfa_design.accepts?('(()(()()))')
=> true

可是这种设计有一个严重的缺陷：如果括号的嵌套等级超过3，它就会失败。它没有足够多的状态跟踪'(((())))' 这样的字符串的嵌套，因此即使括号明显是平衡的它也会拒绝：

>> nfa_design.accepts?('(((())))')
=> false

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

根本问题是一台有限自动机只有固定的状态集合，因而其存储是有限的，因此没法跟踪任意数量的信息。在平衡字符串问题当中，一台NFA 很容易递增到设计时限制的某个最大数目，但无法继续计数以适应任何可能大小的输入。2 本质上大小固定的任务（比如对字符串'abc' 进行匹配），或者无需跟踪重复次数的任务（比如对正则表达式ab*c 进行匹配），都不受这个问题的影响，但在信息数目不可预知，需要在计算过程中存储并在之后重用的场景下，这个问题会让有限自动机无能为力。

2这并不是说一个输入字符串真的可以是无限的，只是说我们可以根据需要让它尽可能有限地大。

正则表达式和嵌套字符串

我们已经看到，有限自动机与正则表达式关系密切。3.3.2 节展示了如何把任意一个正则表达式转换成一台NFA，并且实际上还有一个算法可以把任意NFA 转换回一个正则表达式。3 这告诉我们正则表达式与NFA 等价并且拥有同样的限制，因此也不可能使用正则表达式识别括号组成的平衡字符串，也不能识别所有定义中牵涉嵌套任意深度配对情况的语言。

关于这个缺点，最知名的例子就是正则表达式无法区分有效HTML 和无效HTML（http://stackoverflow.com/a/1732454）这一事实。许多HTML 元素要求开闭标记成对出现，而这些标记自身还可能封装着其他元素，因此有限自动机没有足够的能力读取HTML 字符串，并同时跟踪哪些标记没有配上对以及它们嵌套的深度是多少。

但实际上，现实世界中的“正则表达式”库经常超越正则表达式理论上所拥有的能力。Ruby 的Regexp 对象提供的很多特性都不在正则表达式的形式定义当中，而且这些特性提供的额外能力可以识别更多语言。

Regexp 加强的一点就是可以把一个子表达式用(?<name >) 语法标记，然后在别的地方使用\g<name >“调用”这个子表达式。能够引用自己的子表达式，这使得一个Regexp能够递归调用自身，这让匹配任意深度的成对嵌套成为可能。

例如，尽管NFA 不能匹配括号的平衡字符串（因此理论上说正则表达式也不能），但子表达式调用允许我们写出匹配这种字符串的Regxp。下面就是这个Regxp 的样子：

balanced =
  /
    \A # 匹配开始于字符串的开头
    (?<brackets>     # 叫作 "brackets" 的子表达式开始
      \(         # 匹配左括号
      \g<brackets>*  # 匹配子表达式 "brackets" 零次或者多次
      \)         # 匹配右括号
      )        # 子表达式结束
      *        # 重复整个模式零次或多次
      \z         # 匹配结束于字符串的结尾
    /x

子表达式(?<brackets>...) 匹配一对开闭括号，但在括号内，它还能匹配任意次数的自身，因此整个模式可以正确识别嵌套任意深度的括号：

> ['(()', '())', '(())', '(()(()()))', '((((((((((()))))))))))'].grep(balanced)
=> ["(())", "(()(()()))", "((((((((((()))))))))))"]

这种方式能行，只是因为Ruby 的正则表达式引擎使用了调用栈跟踪(?...)，这是DFA 和NFA 不能做到的。下一节里，我们将看到如何扩展有限自动机，让它也获得这种能力。

是的，你也可以用同样的思想写一个Regxp 匹配嵌套的HTML 标记，但肯定不值得花这个时间。

3简单地说，这个算法通过把一台NFA 转换成广义非确定性有限自动机（GNFA）来完成工作。GNFA是这样一种有限状态机，每一个规则都用一个正则表达式标记（而不是用一个字符标记），然后不断合并这台GNFA 的状态和规则，直到只剩下两个状态和一个规则为止。最后剩下的规则上标记的正则表达式总是与原始NFA 匹配相同的字符串。

很明显这些机器的能力存在局限性。如果非确定性不足以让有限自动机能力更强，那什么才能赋予它更多的能力呢？现在的问题来源是机器有限的存储，因此我们可以增加一些存储看看怎么样。