本文目的：

1.学会正则表达的基本符号；

2.学会画DFA图，解决计算机开始关于DFA表示的全部问题！

-----------------------------------------------------废话分割线----------------------------------------------------

基本概念：

一个正则表达式的基本元素就是字符集。通过对 规则的串联、并联、重复、可选等操作，我们可以构造除更复杂的正则表达式。如果从正则表达式构造状态机的时候也可以用这几种操作对状态图进行组合的话，那 么方法将会变得很简单。接下来我们将一一对这5个构造正则表达式的方法进行讨论。使用下文描述的算法构造出来的所有ε-NFA都有且只有一个结束状态 。

1 字符集 字符集是正则表达式最基本的元素，因此反映到状态图上，字符集也会是构成状态图的基本元素。对于字符集C，如果有一个规则只接受C的话，这个规则对应的状态图将会被构造成以下形式：

这个状态图的初始状态是Start，结束状态是End。Start状态读入字符集C跳转到End状态，不接受其他字符集。

2 串联 如果我们使用A⊙B表示规则A和规则B的串联，我们可以很容易的知道串联这个操 作具有结合性，也就是说(A⊙B)⊙C=A⊙(B⊙C)。因此对于n个规则的串联，我们只需要先将前n-1个规则进行串连，然后把得到的规则看成一个整 体，跟最后一个规则进行串联，那么就得到了所有规则的串联。如果我们知道如何将两个规则串联起来的话，也就等于知道了如何把n个规则进行串联。 为了将两个串联的规则转换成一个状态图，我们只需要先将这两个规则转换成状态 图，然后让第一个状态的结束状态跳转到第二个状态图的起始状态。这种跳转必须是不读入字符的跳转，也就是令这两个状态等价。因此，第一个状态图跳转到了结 束状态的时候，就可以当成第二个状态图的起始状态，继续第二个规则的检查。因此我们使用了ε边连接两个状态图：

3 并联 并联的方法跟串联类似。为了可以在起始状态读入一个字符的时候就知道这个字符可 能走的是并联的哪一些分支并进行跳转，我们需要先把所有分支的状态图构造出来，然后把起始状态连接到所有分支的起始状态上。而且，在某个分支成功接受了一 段字符串之后，为了让那个状态图的结束状态反映在整个状态图的结束状态上，我们也把所有分支的结束状态都连接到大规则的结束状态上。如下所示：

4 重复 对于一个重复，我们可以设立两个状态。第一个状态是起始状态，第二个状态是结束状态。当状态走到结束状态的时候，如果遇到一个可以让规则接受的字符串，则再次回到结束状态。这样的话就可以用一个状态图来表示重复了。于是对于重复，我们可以构造状态图如下所示：

5 可选 为可选操作建立状态图比较简单。为了完成可选操作，我们需要在接受一个字符的时 候，如果字符串的前缀被当前规则接受则走当前规则的状态图，如果可选规则的后续规则接受了字符串则走后续规则的状态图，如果都接受的话就两个图都要走。为 了达到这个目的，我们把规则的状态图的起始状态和结束状态连接起来，得到了如下状态图： 理论知识：

----------------------------------------------前提介绍分割线-------------------------------------------------

NFA是非确定性的状态机，DFA是确定性的状态机。确定性和非确定性的最大区 别就是：从一个状态读入一个字符，确定性的状态机得到一个状态，而非确定性的状态机得到一个状态的集合。如果我们把NFA的起始状态S看成一个集合{S} 的话，对于一个状态集合S’，给定一个输入，就可以用NFA计算出对应的状态集合T’。因此我们在构造DFA的时候，只需要把起始状态对应到S’，并且找 到所有可能在NFA同时出现的状态集合，把这些集合都转换成DFA的一个状态，那么任务就完成了。因为NFA的状态是有限的，所以NFA所有状态的集合的 幂集的元素个数也是有限的，因此使用这个方法构造DFA是完全可能的。 为了形象地表达出这个算法的过程，我们将构造一个正则表达式，然后给出该正则表达式转换成NFA的结果，并把构造DFA的算法应用在NFA上。假设一个字符串只有a、b和c三种字符，判断一个字符串是不是以abc开始并且以cba结束正则表达式如下： abc(a|b|c)*cba 通过上文的算法，可以得出如下图所示的NFA：

如下图所示的DFA：