[Algorithm]Regular Expression and NFA

这篇文章主要介绍正则表达式(Regular Expression)，与如何运用NFA来解决其匹配的问题，主要参考了Princeton Algorithm一书的相关章节。首先我们定义的正则表达式(RE)如下:

• 空串
• 单个字符，其中.可以match任意单个字符
• 被括号括起来的RE
• 两个或两个以上的RE连接
• 两个或两个以上的RE用or(|)隔开
• RE后面跟着closure(*)符号

以上规定了一个正则表达式的语法。具体来说，正则表达式是一系列的字符串的集合，定义如下：

• 空串代表空集
• 单个字符就代表他本身，.代表所有合法字符的集合
• 多个RE相连表示了这多个个集合的叉乘，也就是说每个集合我们都遍历所有的可能
• 多个RE用or隔开表示这多个集合的并集
• closure代表空集或者，RE重复任意多次所构成string的集合

比如对于正则表达式(.B|C(DE)*):

• AB, BCDE, ZBDEDEDE都可以match
• ABC, BDE, CDEDE都不match

那么现在的问题就是对于给定的正则表达式，我们有效的判定每一个输入字符串是否match。在KMP算法当中，我们是用DFA自动机的思想，对于给定的输入的每一个字符，我们根据建立的next数组转移到对应的状态，每接受一次输入，自动机的状态是确定的，所以叫做Deterministic Finite Automata。

但是对于正则表达式，我们没有办法做到这一点，因为or的存在，我们没办法根据当前输入的单个字符确定是否match；同样因为closure，我们不确定要扫多少个字符才能确定不能match。所以DFA是没有办法帮我们解决RE问题的，我们需要更强力的武器，NFA(Non-Deterministic Finite Automata)。

为了理解什么是NFA，我们用正则表达式((A*B|AC)D)举例:

图一就是((A*B|AC)D)所对应的NFA，NFA有如下性质:

• 对于长度为N的RE(每个RE我们用括号括起来)有N + 1个状态，每一个char对应一个状态，最后为accept的状态
• 每一个字母都有一个出向边指向下一个字符所对应的状态(图中黑色边)
• (, ), *, | 都有至少一个出向边，可能指向任何一个其他的状态(图中红色边)
• 有的状态可能有多个出向边，但是只会有一个黑色的出向边

对于所有的RE，我们都在其外圈加一个括号，这样我们每次就都会从左括号出发。同DFA一样，我们每次也读一个字符:

• 如果我们现在处于某个字母所表示的状态，并且读入的字符和其match，我们从黑色的边转移到下一个状态，我们称其为match transition。
• 我们可以在不扫描输入字符的情况下，直接沿着红边进行状态转移。比如我们在start state 0的时候，我们可以不match任何输入字符，到达1, 2, 3, 4, 6。我们称之为ε-transition

因为ε-transition的存在我们事实上是从一个状态的集合向另一个状态的集合转移。这样我们每一次的match输入字符串的步骤为:

1. DFS找到所有可能的初始状态的集合
2. 每一次扫描输入字符，对于当前的集合，找到对应进行match transition的之后的状态集合，
3. 再DFS找到所有进行ε-transition可以到达的集合。重复步骤2和3，直到扫描完所有输入字符
4. 看当前状态的集合是否包括accpet状态

我们拿((A*B|AC)D)和AABD举例，下图表示了每个步骤具体的操作：

时间复杂度分析，假设RE长为M，待匹配串长度为N，时间复杂度为O(N * M)，对于每一个输入字符，我们最多需要找N个状态。

那么剩下的问题，就是对于一个RE，我们如何建立对应的NFA。我们需要一个栈来存一些特殊的字符，比如括号和or，对于每一个不同的字符:

• 当前字符如果是普通字母或者是. ，这是最简单的状况，会有一条黑色的出向边连接下一个状态
• 当前字母是括号，对于左括号，我们直接放上stack。对于右括号，我们pop栈上的字符直到左括号，对应字符的操作见下文
• 对于包含or的RE，例如(A | B)，我们需要建立两条对应ε-transition的边，一条从左括号到B，对应我们可以直接跳过A到达B；另一条从| 到达右括号，对应我们如果match了A就要跳过之后的。如果有多个or的符号也是一样的。我们每次push or对应的index到栈上，碰到右括号之后，就一直pop直到左括号，碰到or符号的话，我们就建立对应的两条边
• 对于closure，其有两种情况
• 单个字符后面接closure，这样我们建一条从字符到closure的边，另一条从closure回到字符的边，两条ε-transition边
• RE带括号后面接closure，这样我们需要从左括号到closure建立两条对应的边

下图表明了对应不同符号应该建立的边：

值得一提的是，在我们真正建图的时候，只需要建立所有的ε-transition，matching transition并不需要刻意建，因为其事实上就是从当前字符转移到下一个字符。

我们仍然拿((A*B|AC)D)距离，对应的步骤如下：

时间复杂度方面，对于长度为N的RE，时间复杂度为O(N)，因为我们每次最多加三条边。空间复杂度也是O(N)，代码如下