4.1. 正则表达式¶
4.1.1. 正则表达式¶
正则表达式 （RegEx 或 R.E.）是一种指定字符串集合，从而定义一种语言的方式。
可以使用三种运算符：
\(+\) 并（union）（OR）
\(\cdot\) 连接（concatenation）（AND）
\(*\) 星闭包（star-closure）（重复 0 次或多次）
我们常常省略表示连接（concatenation）的 \(\cdot\)。
定义： 给定 \(\Sigma\)，
\(\emptyset\)、\(\lambda\) 和 \(a \in \Sigma\) 都是 R.E.。
如果 \(r\) 和 \(s\) 是正则表达式，那么
\(r + s\) 是一个 R.E.。
\(r s\) 是一个 R.E.。
\((r)\) 是一个 R.E.。
\(r^*\) 是一个 R.E.。
\(r\) 是 R.E.，当且仅当它能通过有限次应用（2） 从（1）推导出来。
定义： \(L(r)\) 是由正则表达式 \(r\) 表示的语言。
\(\emptyset\)、\(\{\lambda\}\) 和 \(\{a \in \Sigma\}\) 各自都是由某个 R.E. 表示的语言。
注意，\(\emptyset = \{\}\) （空集），而 \(\lambda = \{ \lambda \}\)，表示仅包含空字符串的集合。问：每个正则语言都包含空字符串吗？
如果 \(r\) 和 \(s\) 是 R.E.，那么
\(L(r + s) = L(r) \cup L(s)\)
\(L(r s) = L(r) \cdot L(s)\)
\(L((r)) = L(r)\)
\(L((r)^*) = (L(r)^*)\)
4.1.1.1. 优先级规则¶
\(*\) 优先级最高
\(\cdot\)
\(+\) 优先级最低
例：\(ab^* + c = (a(b)^*) + c\)
4.1.1.2. 正则表达式示例¶
\(\Sigma = \{a,b\}\)， \(\{w \in {\Sigma}^{*} \mid w\) 含奇数个 \(a\)，后面跟着偶数个 \(b\) \(\}\)。
\((aa)^{*}a(bb)^{*}\)
问：这种语言包含空字符串吗？
\(\Sigma=\{a,b\}\)，\(\{w \in {\Sigma}^{*} \mid w\) 至多有 三个 \(a\) 且必须以 \(ab\}\) 结尾。
\(b^{*}(ab^{*} + ab^{*}ab^{*} + \lambda)ab\)
正负整数的正则表达式
\(0 + (- + \lambda)((1+2+\ldots +9)(0+1+2+\ldots +9)^{*})\)
问：对于这种语言，什么可接受，什么不可接受？
问：每个有限字符串集都能用 R.E. 描述吗？你应该能够回答这个问题。
既然我们已经定义了什么是正则表达式，一个值得问的问题是：我们为什么需要它们？特别是，我们已经知道两种定义语言的方式。一种是从概念上，用或多或少具有数学精确性的英语描述。另一种是在操作上采用 DFA（或等价地，NFA）的形式。那么，为什么还需要另一种表示？一个好的答案是，其他两种表示各有缺陷（方式不同），而正则表达式正好克服了这些缺陷。用英语描述不精确。即使我们借助数学使其精确，那也是我们不容易操作化（operationalize）的东西。另一方面，定义 DFA（或 NFA）有点耗时。我们可以使用像 JFLAP 或 OpenFLAP 这样的工具，但即使机器相对较小，在图形界面（GUI）中操作也需要相对较长的时间。相比之下，我们可以直接在像 JFLAP 这样的系统中输入一个正则表达式。这样，无论是输入还是操作化（operationalize）都很快（就后者而言，我们可以随后把 RegEx 转换为 DFA，从而为这个正则表达式实现接受器）。当然，程序（或机器）可长可短，但我们可能很难想出这个程序。同样，我们也许不得不绞尽脑汁想出正则表达式。但一旦想出来了，输入起来可能很短。
4.1.2. 正则表达式与正则语言¶
回想一下，我们 定义 术语 正则语言 是指被 DFA 识别的语言。（我们知道这与被 NFA 识别的语言相同，因为每个 NFA 都能被转换为 DFA。）正则表达式与这些有什么关系？它们是相同的语言吗？其中一个是另一个的子集吗？还是说它们只是不同的语言集合？
我们可以很容易地看出 \(\emptyset\)、\(\lambda\) 和 \(a \in \Sigma\) 的 NFA。
下面是一个什么都不接受（\(\emptyset\)）的 NFA。
下面是一个接受空字符串（\(\lambda\)）的 NFA。
下面是一个接受 \(a \in \Sigma\) 的 NFA。
但那些由 AND、OR 和连接（concatenation）构成的"更有意思"的正则表达式呢？它们都有对应的 NFA 吗？如果我们能找到一种方法，用 NFA"模拟"这每一种运算，那么我们就知道可以为任何 R.E. 构造机器。这种"模拟"的思想是证明这类结论的标准方法！
假设 \(r\) 和 \(s\) 是 R.E.（由归纳法……）这意味着存在用于 \(r\) 的 NFA 和用于 \(s\) 的 NFA。为了帮助我们直观地理解这些内容，如果能有标准方式来画出任意 NFA 的结构，会很有帮助。而且，因为我们想把机器组合在一起，如果知道任意机器只有一个开始状态和一个终止状态，事情就会容易得多。嗯，我们已经知道所有 NFA 都只有一个开始状态。但并不是所有 NFA 都只有一个终止状态。
备注
考虑任意 NFA 及其各种终止状态。有没有一种简单的方法把它转换为具有 单一终止状态 的 等价 NFA ？答案是"有"，方法是添加一个新状态作为机器的终止状态。请自己想清楚如何做到这一点。
下面的幻灯片展示了如何把具有多个终止状态的 NFA 转换为只有一个终止状态的 NFA。
我们的下一步是展示如何针对每个 R.E. 运算符，在其操作数 NFA 上构建实现该运算符行为的 NFA。
OR：\(r + s\)。
这意味着我们有 NFA \(r\) 和 \(s\)，想要一个新的 NFA 把它们 OR 在一起。只需添加一个新的开始状态和一个新的终止状态，各自（并行地）用 \(\lambda\) 转移同时连接到 \(r\) 和 \(s\)。
\(r \cdot s\)：添加新的开始状态和新的终止状态，并用 \(\lambda\) 转移把它们串联起来。
\(r^*\)：添加新的开始状态和终止状态，以及允许在所有状态之间自由移动的 \(\lambda\) 转移。
例题： \(ab^* + c\) （多终止状态）
下面是一个接受 \(ab^* + c\) 的 NFA。
既然我们有了接受 \(ab^* + c\) 的 NFA，就可以把它转换为 DFA，然后再转换为最小化 DFA。
备注
此时，你应该去 OpenFLAP 亲自试一试。输入 R.E.，然后把它转换为 NFA，再把 NFA 转换为 DFA，最后最小化 DFA。
你应该会注意到，当 OpenFLAP 自动把 R.E. 转换为 NFA 时，得到的 NFA 看起来并不像上面示意图中的"直观"版本。这是因为自动化的过程稍微复杂一些。要理解算法如何自动地把 R.E. 转换为 NFA，其中许多步骤不外乎是用本模块前面图表中的变换来构建机器—例如把两个机器组合起来进行 OR 或 AND 等。
定义： 广义转移图（Generalized Transition Graph，GTG）是一种边可以用任意正则表达式标注的转移图。因此，它是对标准转移图的"推广"。
从 R.E. 自动转换为 NFA 的过程，只是从最低优先级的运算符（OR）开始，一步步遍历 R.E.，把 R.E. 分解成若干部分机器，再组合在一起。正如这里所见，这是一个相当简单的过程。
这个例子应该说明的一点是：NFA 的概念对我们的理解确实很有帮助。虽然每个 NFA 都 可以被等价的 DFA 取代，但直观地理解把 R.E. 转换为 NFA 的过程，比直接构造 DFA 要容易得多。
最后，这里有一个幻灯片，展示了自动化过程把 R.E. 转换为最小化 DFA 时所经历的全部细节。
4.1.3. 把正则语言转换为正则表达式¶
既然每个正则表达式都有实现它的 NFA，这意味着正则表达式是正则语言的子集。下一个问题是：每个正则语言都有对应的正则表达式吗？
定理： 设 \(L\) 是正则的。那么存在一个 R.E.，使得 \(L = L(r)\)。
也许你认为任何正则表达式都能实现为 NFA（如前所述）是相当直观的。但对大多数人来说，任何 NFA 都能转换为正则表达式这一点并不明显。这个证明相当困难，我们只给出一个概要。
定义： 完全 GTG 是完全图，意味着每个状态都有一条到其他每个状态的转移。任何 GTG 都可以通过按需添加标注为 \(\emptyset\) 的边来转换为完全 GTG。
证明：
\(L\) 是正则的 \(\Rightarrow \exists\) NFA \(M\)，使得 \(L = L(M)\)。
假设 \(M\) 只有一个终止状态，且 \(q_0 \notin F\)。
把 \(M\) 转换为完全 GTG。
设 \(r_{ij}\) 表示从 \(q_i\) 到 \(q_j\) 的边的标签。
如果 GTG 只有两个状态，那么它具有如下形式：
在开始状态上添加一个箭头。那么，对应的正则表达式为：
\(r = (r^*_{ii}r_{ij}r^*_{jj}r_{ji})^*r^*_{ii}r_{ij}r^*_{jj}\)
当然，我们可能有一个机器，其开始状态同时也是终止状态。处理这种情况有两种方法。一种是针对这种情况提出一条规则。（提示：这是同一条规则，只是为停留在开始状态的情况额外添加一个"OR"。）另一种是先把我们的 NFA 转换为只有一个终止状态（与开始状态分开）的 NFA。这很容易做到，很可能还是班级作业。
如果 GTG 有三个状态，那么它一定具有如下形式：
在这种情况下，做如下替换：
\[\begin{split}\begin{array}{lll} REPLACE & \ \ \ \ \ \ \ \ & WITH \\ \hline r_{ii} && r_{ii}+r_{ik}r_{kk}^{*}r_{ki} \\ r_{jj} && r_{jj}+r_{jk}r_{kk}^{*}r_{kj} \\ r_{ij} && r_{ij}+r_{ik}r_{kk}^{*}r_{kj} \\ r_{ji} && $r_{ji}+r_{jk}r_{kk}^{*}r_{ki} \\ \end{array}\end{split}\]完成这些替换后，移除状态 \(q_k\) 及其边。
如果 GTG 有四个或更多状态，请选择任何一个不是起始状态或最终状态的 \(q_k\) 状态。该状态将被移除。对于所有 \(o \neq k, p \neq k\) ，将 \(r_{op}\) 替换为 \(r_{op} + r_{ok}r^*_{kk}r_{kp}\) 。
完成后，移除 \(q_k\) 及其所有边。继续消除状态，直到只剩下两个状态。最后用第（3）步收尾。
在每一步中，我们可以用以下适用的规则来简化正则表达式 \(r\) 和 \(s\)：
\(r + r = r\) （子集与自身 OR，得到的仍是同一个子集）\(s + r{}^{*}s = r{}^{*}s\) （子集与更大的子集 OR ，得到的就是更大的子集）\(r + \emptyset = r\) （子集与空集 OR ，结果仍只是该子集）\(r\emptyset = \emptyset\) （子集与空集相交 ，得到空集）\(\emptyset^{*} = \{\lambda\}\) （特殊情况）\(r\lambda = r\) （先经过一个 R.E.，再做一次自由转移 ，仍只是同一个 R.E.）\((\lambda + r)^{*} = r^{*}\) （进行一次自由转移不会增加任何东西。）\((\lambda + r)r^{*} = r^{*}\) （可以额外选择多做一次 \(r\) 不会增加任何东西）以及其他类似的规则。
你应该让自己相信，在这张图中，右侧是对左侧的恰当重建。换句话说，右侧机器中给左侧状态的自环标注的 R.E.，正确地刻画了停留在左侧机器状态 \(q_0\) 的所有方式。同样，右侧机器中给从左侧状态到右侧状态的边标注的 R.E.，也正确地刻画了在左侧机器中从 \(q_0\) 到 \(q_2\) 的所有方式。
我们现在已经证明正则表达式与 DFA 等价。也就是说，给定任何正则表达式，我们都有一个算法把它转换为某个 DFA。反之亦然。
