3079人阅读
数据结构与算法（15）
一个问题：Beautiful
这是2014微软校招的编程题，题意大致如下：
如果一个字符串包括三组或者更多组的连续升序字母，每组长度相等，那么我们就称这个字符串是Beautiful String
符合Beautiful String举例：abc, cde, aabbcc, aaabbbccc不符Beautiful String举例：abd，cba，aabbc，zab
输入一个只含有小写字母的字符串，如果它含有一个Beautiful的子串，就输出YES，否则输出NO输入： 第一行是案例个数，之后的每一行是一个数字，一个字符串，数字表示字符串长度，长度小于10MB输出：YES 或 NO
有限状态机
又称有限状态自动机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。常用与：正则表达式引擎，编译器的词法和语法分析，游戏设计，网络协议，企业应用中等方面。
有限状态机
状态机可归纳为4个要素，即现态、条件、动作、次态。这样的归纳，主要是出于对状态机的内在因果关系的考虑。
“现态”和“条件”是因，“动作”和“次态”是果。
1. 现态：是指当前所处的状态。
2. 条件：又称为“事件”，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
3. 动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态 。
4. 次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。
有限状态机
用while{switch/case}(推荐可读性高) 或 if/else 实现，简单粗暴，适合简单的小型状态机；用设计模式中的 state pattern，把复杂判断的逻辑简化，利于组织代码；用状态表设计，建立状态表和动作查询表，根据状态表、事件、动作表定位相应的动作处理函数，执行完成后再进行状态的切换；
Beautiful String问题的解法
这个自动机规模小，直接用if/else简单的实现即可。每个状包含4个要素：
当前处理的字符 current当前处理的字符数量 num_currentBeautiful String中上一个字符的数量 num_prev当前元素是Beautiful String中第几个元素 pos_beauty
#include&iostream&
struct states {
正在处理的字符
beautiful string中上一个元素的数量
正在处理的字符累计的数量
正在处理的字符是 beautiful string中的第几个元素
} s = { 0, 0, 0, 0 };
int main() {
int ncase,
while (ncase--) {
bool result =
while (n--) {
if (result) {
if (s.current == 0) {
s.current =
s.num_current = 1;
s.pos_beauty = 1;
if (s.current == c) {
s.num_current++;
if (s.num_prev != 0 && s.num_current & s.num_prev) {
s.num_prev = 0;
s.pos_beauty = 1;
if (s.current == c - 1) {
if (s.num_prev == 0 || s.num_current &= s.num_prev) {
s.pos_beauty++;
s.pos_beauty = 2;
s.num_prev = s.num_
s.num_current = 1;
if (s.current != c && s.current != c - 1) {
s.pos_beauty = 1;
s.num_current = 0;
s.num_current = 1;
if (s.pos_beauty &= 3 && s.num_current == s.num_prev) {
s.current =
if (result) {
cout && "YES" &&
cout && "NO" &&
aaaabbbccde&&&&&&游戏智能是很传统的领域，有限状态机和行为树是两种主要方法。今天这篇博客主要介绍有限状态自动机。
1. 有限状态机
&&&&&&有限状态机 (Finite-state machine，FSM)，又称有限状态自动机，是表示有限个状态以及状态之间转移和动作等行为的数学模型。从它的定义，我们可以看到有限状态机的几个重要概念。
1.状态：表示对象的某种形态，在当前形态下可能会拥有不同的行为和属性;
2.转移：表示状态变更，并且必须满足确使转移发生的条件来执行;
3.动作：表示在给定时刻要进行的活动;
4.事件：事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。
&&&&&&下图是一个典型的有限状态机，描述了一个简单的对战逻辑。
这个有限状态机有三个状态，分别是 idle, escape 和 不同状态之间的转换是通过动作进行的，比如 idle 状态看到哥布林就会进入 attack 状态。
2. Clashjs 游戏中的有限状态机
&&&&&&但是在 Clashjs 游戏中，有限状态机需要一些变化。因为 Clashjs 游戏中，一架飞机的状态不仅由它本身采取的动作决定，还由它所处的环境（包括敌机和弹药包）决定。这时候的有限状态机反而简单了，不考虑状态之间的切换，只考虑在每个状态下应该采取什么动作。Clashjs 游戏中的有限状态机的实现代码如下所示。完整的代码已经传到 GitHub 上了（）。
if (utils.canKill(playerState, enemiesStates) && playerState.ammo) {
return 'shoot';
if (direction2ammo !== playerState.direction && direction2ammo !== null) {
return direction2
if (direction2ammo == playerState.direction){
return 'move';
return utils.safeRandomMove();
由于状态转移部分在游戏逻辑中，有限状态机代码退化成什么状态采取什么动作的 if-else 语句了。上图实现的有限状态机的示意图如下。
&&&&&&最近为了写游戏智能系列文章，我了解了一些游戏智能相关知识。我发现和如火如荼的机器学习和虚拟现实一比，游戏智能简直就是南极的冰窟窿。例如，我们很难找到这个领域的好资料和交流圈，特别是有关实操相关的资料。我想原因有两个。第一，游戏智能不 sexy。游戏智能的算法都只是一个框架，具体游戏行为逻辑需要大量人力物力填写，比端到端的深度学习不知道低到哪里去了。第二，游戏智能不容易复现因此比较难学习。机器学习有很多公开的数据集。拿到这些数据集，我们就可以写代码调参数了。但是游戏智能和游戏紧密结合，大部分好的游戏不提供游戏智能的接口，大部分提供接口的游戏质量差强人意。这使得非游戏开发商内部人员很难有机会实践游戏智能，从而很难产生好的实操分享。虽然说了那么多坑，但自己选得路，跪着也要走完。我会努力写完游戏智能系列。
&&&&&&欢迎关注我的公众号，每周日的更新就会有提醒哦~
游戏智能系列之三:有限状态自动机
此条目发表在, 分类目录，贴了, 标签。将加入收藏夹。
每周日更新，不关注下么？27被浏览7,106分享邀请回答2添加评论分享收藏感谢收起第 10 章　模式、自动机和正则表达式
第 10 章　模式、自动机和正则表达式
模式是具有某个可识别属性的对象组成的集合。字符串集合就是一类模式，比如C语言合法标识符的集合，其中每个标识符都是个字符串，由字母、数字和下划线组成，开头为字母或下划线。另一个例子是由只含0和1的给定大小数组构成的集合，读字符的函数可以将其解释为表示相同符号。图10-1就展示了全都可以解释为字母A的3个7×7数组。所有这样的数组就可以构成模式“A”。
0001000　　　0000000　　　00010000011100　　　0010000　　　00101000010100　　　0011000　　　01101000110110　　　0101000　　　01111100111110　　　0111000　　　11000111100011　　　1001100　　　10000011000001　　　1000100　　　0000000
图 10-1　模式“A”的3个实例
与模式相关的两个基本问题是它们的定义与它们的识别，这是本章以及第11章的主题。模式的识别是诸如图10-1所示的光学字符识别（Optical Character Recognition，OCR）这样的任务中不可或缺的一部分。在某些应用中，程序中模式的识别是编译过程，也就是将程序从一种语言（比方说C语言）翻译成另一种语言（比如机器语言）的过程的一个重要部分。
模式应用在计算机科学中还有其他很多例子。模式在设计用于组成计算机和其他数字设备的电子电路的过程中扮演着关键的角色。它们也可以用在文本编辑器中，让我们可以查找特定单词或特定字符串集合的实例，比如“字母if之后跟着任意由then开头的字符序列”。大多数操作系统允许用户在命令中使用模式，例如，UNIX命令“ls *tex”就会列出所有以3字符序列“tex”结尾的名称。
人们围绕着模式的定义和识别建立起了一套庞大的知识体系。这一理论被称为“自动机理论”或“语言理论”，而其基本定义和技术都是计算机科学的核心部分。
10.1　本章主要内容
本章处理的是由字符串集合组成的模式，我们在本章中将会学习以下内容。
“有限自动机”是一种基于图的模式指定方式。有限自动机又分为两种：确定自动机（10.2节）和非确定自动机（10.3节）。
可以用简单的方法把确定自动机转换成识别其模式的程序（10.2节）。
可以利用10.4节介绍的“子集构造”，把非确定自动机转换成识别相同模式的确定自动机。
正则表达式是种代数，用来描述可由自动机描述的同类模式（10.5节到10.7节）。
正则表达式可转换为自动机（10.8节），反之亦然（10.9节）。
我们还要在第11章中讨论串模式，其中会引入一种名为“上下文无关文法”的递归表示法来定义模式。我们将看到这种表示法可以描述没法用自动机或正则表达式表示的模式。不过，在很多情况下，文法都不如自动机或正则表达式那样容易转换为程序。
10.2　状态机和自动机
用来查找模式的程序通常有着特殊的结构。我们可以在代码中确定某些位置，在这些位置可以得知与程序寻找模式实例的过程有关的特殊信息。我们将这些位置称为状态。而程序的整体行为可以视作程序随着读入输入从一种状态转移到另一种状态。
要让这些概念变得更具体，可以考虑一个具体的模式匹配问题：“哪些英语单词按次序含有5个元音字母？”要回答这一问题，可以使用很多操作系统中都能找到的单词表。例如，在UNIX系统中可以在文件/usr/dict/words中找到这样的表，表中每一行都含有一个常用单词。在该文件中，一些含多个元音字母的单词是按以下次序排列的：
abstemious
sacrilegious
我们来编写一个简单的C语言程序，检查某个字符串并确定5个元音字母是否按次序出现在该字符串中。从字符串的开头开始，该程序首先会查找到a。我们会说该程序处于“状态0”，直到它发现一个a，然后它就进入“状态1”。在状态1中，它会查找字母e，而且当它找到一个之后，就会进入“状态2”。该程序会继续按照这种方式运行，直至到达查找字母u的“状态4”。如果它找到u，那么该单词就是按次序含有5个元音字母，这个程序就能进入一个用于接受的“状态5“。不需要再扫描单词的其余部分，因为已经可知，不管u后面有哪些字母，该单词都是满足条件的。
可以这样解释状态i，就是对i=0、1、…、5，程序已经按次序遇到了前i个元音字母。这6个状态总结了程序在从左到右扫描其输入的过程中需要记住的所有内容。例如，在状态0中，尽管该程序在查找a，但它不需要记住是否已经看到了e。原因在于这样的e不可能先于任何a，因此不能作为序列aeiou中的e。
这种模式识别算法的核心是图10-2中的findChar(pp,c)函数。该函数的参数是pp——指向字符串的指针的地址，以及所需的字符c。也就是说，pp是“指向指向字符的指针的指针”。函数findChar会查找字符c，并且顺便会移动已给定地址的指针，直到该指针指向超过字符c或该串结尾的位置。它返回BOOLEAN类型的值，就是我们定义的与int相同的类型。正如在1.6节中讨论过的，我们预期BOOLEAN类型的值只有TRUE和FALSE，它们分别被定义为1和0。
在第(1)行，findChar会检查当前由pp指示的字符。如果它既不是所需的字符c，也不是C语言中标记字符串末端的字符“\0”，那么在第(2)行我们会移动pp指向的该指针。第(3)行的测试会确定我们是否因为遍历完该串而停止。如果是，就返回FALSE，否则前移该指针并返回TRUE。
#include &stdio.h&
#define TRUE 1
#define FALSE 0
typedef int BOOLEAN;
BOOLEAN findChar(char **pp, char c)
while (**pp != c && **pp != '\0')
if (**pp == ’\0’)
return FALSE;
return TRUE;
BOOLEAN testWord(char *p)
/* 状态 0 */
if (findChar(&p, 'a'))
/* 状态 1 */
if (findChar(&p, 'e'))
/* 状态 2 */
if (findChar(&p, 'i'))
/* 状态 3 */
if (findChar(&p, 'o'))
/* 状态 4 */
if (findChar(&p, 'u'))
/* 状态 5 */
return TRUE;
return FALSE;
printf("%d\n", testWord("abstemious"));
图 10-2　找到带有子序列aeiou的单词
在图10-2中，接下来是testWord(p)函数，它可以区分由p指向的字符串是否按次序含有所有元音字母。该函数在第(7)行前从状态0开始。在该状态中它在第(7)行调用findChar，其中第二个参数是a，用来查找字母a。如果它找到了a，findChar就会返回TRUE。因此在第(7)行如果findChar返回了TRUE，程序就会转移到状态1，其中在第(8)行会对e进行相似的测试，从第一个a之后开始扫描该字符串。因此它会继续查找元音字母，直到第(12)行，如果它找到了字母u，就会返回TRUE。如果有任何一个元音字母未被找到，控制权就会转移到第(13)行，在该行中testWord会返回FALSE。
第(14)行的主程序会测试特定的字符串“abstemious”。在实践中，我们可能会对文件中的所有单词反复使用testWord，以找出那些按次序含有5个元音字母的单词。
10.2.1　状态机的图表示
我们可以把图10-2中这种程序的行为用图表示出来，其中图的节点表示该程序的各个状态。更重要的可能在于，可以通过设计图从而设计出程序，并机械化地将图转化成程序，要么自己动手做，要么利用某种为这个目的编写的程序设计工具。
表示程序状态的图都是有向图，它们的弧都是用字符集标记的。如果当我们在状态s 时，刚好只有当看到集合C 中的一个字符时才能行进到状态t，就存在从状态s 到状态t 的标号为字符集C 的弧。这些弧叫作转换（transition）。如果x 是字符集C 中的某个字符，它标记了从状态s 到状态t 的转换，就说“进行了针对x 的到状态t 的转换”。在集合C 为单元素集{x }这种常见的情况下，我们会使用x 作为该弧的标号，而不用{x }。
我们还会给某些节点标记接受状态（accepting state）。当到达这些状态之一时，就找到了模式并要“接受”它。按照惯例，接受状态是用双层圆圈表示的。最后，这些节点之一会被指定为起始状态，也就是开始模式识别过程所在的状态。我们用一条不知道来自何方的进入箭头表示起始状态。这样的图就被称为有限自动机，或就叫自动机。在图10-3中可以看到自动机的一个例子。
图 10-3　识别含子序列aeiou的字符序列的自动机
从概念上讲，自动机的行为其实很简单。可以想象，自动机接收一列已知字符作为输入序列。它从起始状态开始读输入序列的第一个字符。根据第一个字符的不同，它进行的转换可能是转换到同一状态，也可能是转换到另一状态。这种转换可用自动机的图来表示。然后自动机会读第二个字符，并作出合适的转换，等等。
对应图10-2中testWord函数的自动机如图10-3所示。在该图中，我们使用了下面都要遵守的一个约定，用希腊字母Λ（拉姆达）代表所有大写字母和小写字母组成的集合。还要用Λ-a这样的简写形式表示除a之外所有大小写字母组成的集合。
节点0是起始状态。针对除了a之外的任意字母，我们都会保持状态0，不过遇到a就要进入状态1。同样，一旦到达状态1，就会停留在状态1，除非看到e，在看到e的情况下就要进入状态2。接下来，当看到i然后看到o时就分别到达状态3和状态4。除非看到u并进入唯一的接受状态——状态5，否则我们会停留在状态4中。再没有任何从状态5出发的转换了，因为我们不再检测待测单词的其余字符，而是要返回TRUE，声明我们已成功完成测试。
在状态0到状态4中遇到空白（或其他非字母字符）也是没有价值的，我们不会进行任何转换。在这种情况下，处理会停止，而且，因为我们现在未到达接受状态，所以会拒绝该输入。
接下来的例子来源于信号处理。这里不再把所有字符作为自动机可能接收到的输入，而是只允许输入0和1。我们要设计的这种特殊自动机有时也称为反弹过滤器（bounce filter），它接受0和1组成的序列作为输入。该自动机的目的就是“平滑”该序列，方法是将由1包围的一个0当作“噪音”，并把这个0替换为1。同样，由0包围的一个1也会被当作噪声并被0替代。
这里举一个反弹过滤器使用方式的例子，我们可以逐行扫描某数字化的黑白图像。该图像的每一行其实都是0和1组成的序列。因为图片有时候会因胶片瑕疵或拍摄问题造成有一些小点颜色错误，所以，为了减少图像中不同区域的数量，并让我们将精力放在“真实”的特色而非那些虚假的特征上，消除这样的点是很实用的。
图10-4表示的就是对应该反弹过滤器的自动机。其中的4种状态解释如下：
(a) 我们已经看到至少在一行中含两个0的一列0；
(b) 我们已经看到一列0后面跟着一个1；
(c) 我们已经看到至少有两个1的一列1；
(d) 我们已经看到一列1后面跟着一个0。
状态a 被指定为起始状态，表示我们的自动机进行处理时就好像在输入之前有一个看不见的前缀0序列那样。
图 10-4　消除虚假的0和1的自动机
接受状态是c 和d。对该自动机而言，其接受过程与图10-3所示的自动机有着一些不同的含义。对图10-3所示的自动机而言，在到达接受状态时，就可以说整个输入都被接受了，包括自动机还没有读到的那些字符。1而在这里，我们想要接受状态表述“输出一个1”，还要一个表述“输出一个0”的非接受状态。在这种解释下，我们会将输入中的每一位都转化成输出中的每一位。通常输出是和输入相同的，不过有时候也会不同。例如，图10-5展示了输入为0101101时的输入、各个状态和它们的输出。
1不过，通过为状态5加一个所有字母上的转换，我们可以修改该自动机，使其能继续读u之后的所有字母。
图 10-5　图10-4中的自动机处理输入0101101时的情况模拟
我们从状态a 开始，因为a 是非接受状态，所以输出0。请注意，这一初始输出并不是对任意输入的回应，而是表示在初次开启设备时自动机的条件。
图10-4中从状态a 出发标记了输入0的转换是到达状态a 自身的。因此第二个输出还是0。第二个输入是1，而且从状态a 可以进行针对1的到状态b 的转换。该状态“记住了”我们已经看到过一个1，不过因为b 是非接受状态，所以输出仍然是0。针对第三个输入，也就是另一个0，我们又从状态b 回到了状态a，而且继续发出输出0。
接下来的两个输入都是1，可以先将自动机带到状态b，然后带到状态c。对这两个1中的第一个1，我们发现自己是在状态b 中，这会带来输出0。这个输出是错的，因为我们其实已经开始处理1了，但是在读完第四个输入后还不知道这一点。这种简单设计的影响在于，不管是0还是1组成的，所有的串都被右移了一位，因为在自动机意识到它已经开始处理新的串而不是“噪声”位之前，一行中已经接受了2位。在接收第5个输入时，我们就会遵循从状态b 到状态c 针对输入1的转换。在这一情况下，会得到第一个1输出，因为c 是接受状态。
最后两个输入是0和1。0把我们从状态c 带到状态d，这样我们可以记得自己已经看到了一个0。从状态d 的输出依然是1，因为该状态是接受状态。最后的1将我们带回状态c 并生成输出1。
自动机与其程序之间的区别
自动机是种抽象。从10.3节起将会变得明确，通过确定从起始状态到某个用相应序列标记的接受状态之间是否存在路径，自动机呈现了一种对任意输入字符序列的接受/拒绝决定。举例来说，图10-5表示的反弹过滤器自动机的行为告诉我们，该自动机拒绝ε、0、01、010和0101这些前缀，但它接受0和0101101这几个前缀，如图10-4所示。图10-3的自动机接受abstemiou这样的字符串，但拒绝abstemious，因为从状态5没办法到达最后的s。
另一方面，由自动机创建的程序能以多种方式使用这种接受/拒绝决定。例如，图10-2中的程序使用了图10-3所示的自动机，但它不是认可标记通向接受状态的路径的字符串，而是认可整行输入，也就是，接受abstemious而非abstemiou。这是绝对合理的，而且反映了我们编写程序测试按次序的5个元音字母的方式，而不管是使用了自动机或是其他的方法。据推测，只要我们到达字母u，该程序就会打印出整个单词而不再继续检查其余字母。
图10-4所示自动机的使用方式就更简单。我们将会看到，图10-7中对应这一反弹过滤器的程序会直接把每个接受状态转化成打印一个1的行动，而将每个拒绝状态转化成打印一个0的行动。
10.2.2　习题
1. 设计自动机，读由0和1组成的串，并能进行下述操作。
(a) 确定目前位置读到的序列是否有偶校验（即存在偶数个1）。特别要指出的是，如果目前为止该串有偶校验，则该自动机会接受它，而如果它具有奇校验，自动机就会拒绝它。
(b) 检验输入串没有两个以上连续的1。也就是说，除非111是当前为止读过的输入串的子串，否则接受。
每种状态的直觉含义各是什么？
2. 在给定输入时，指出习题(1)中自动机的状态序列和输出。
3. * 设计自动机，读的是单词（字符串），并分辨单词中的字母是否是已排好序的。例如，adept和chilly这样的单词中的字母就是已排好序的，而baby就不是，因为在第一个b后面有个a。单词一定是以空白终止的，这样自动机才会在读完所有字符后知道这一点。与示例10.1不同，这里我们必须在读完所有字符后才能接受，也就是说，必须在到达单词末端的空白之后才能接受。该自动机需要多少种状态？每种状态的直觉含义是什么？从每种状态出发的转换又有多少？总共有多少种接受状态？
4. 设计自动机，使其能分辨字符串是否为合法的C语言标识符（字母后跟上字母、数字或下划线）后跟上空白。
5. 编写C语言程序，实现习题1到习题4的各种自动机。
6. 设计自动机，使其能分辨给定的字符串是否为第三人称单数代词（he、his、him、she、her或hers）后跟上空白。
7. * 将习题(6)设计的自动机转换成C语言函数，并在程序中使用该函数找到某给定字符串中所有出现第三人称单数代词子串的位置。
10.3　确定自动机和非确定自动机
使用自动机进行的最基本的操作之一是接受一系列的符号a1a2…ak，并从起始状态起循着一条由标号依次为这些符号的弧组成的路径行进。也就是说，对i=1、2、…、k 来说，ai 都是集合Si 中作为路径上第i 条弧标号的成员。构建这一路径及其状态序列的过程就是自动机对输入序列a1a2…ak 的模拟（simulating）。可以说这一路径标号为a1a2…ak，当然，它也可能有其他标号，因为给路径上的弧提供标号的各集合Si 可能各自含有很多字符。
我们在图10-5中进行过一次这样的模拟，其中模仿了图10-4中的自动机对序列0101101的处理。另外，以图10-3中用来识别单词中是否含有序列aeiou的自动机为例，考虑对字符串adept的处理。
我们从状态0中开始。从状态0出发的转换有两次，一次是针对字符集Λ-a的转换，另一次是针对单独一个字母a的。因为adept的第一个字符就是a，所以要遵循后一个转换，这把我们带到了状态1。从状态1出发，又有针对Λ-e和e的转换。因为第二个字符是d，所以必须遵循前一种转换，因为Λ-e包含除了e之外的所有字母。这把我们再次留在状态1中。因为第三个字母是e，所以要循着从状态1出发的第二种转换，将我们带到状态2。adept的最后两个字母都在集合Λ-i中，所以下两次转换都是从状态2到状态2。因此在状态2中就完成了对adept的处理。相应的状态转换序列如图10-6所示。因为状态2不是接受状态，所以我们没有接受输入adept。
图 10-6　对10-3中的自动机针对输入adept的模拟
有关自动机输入的术语
在这里将要讨论的例子中，自动机的输入是字符，比如字母和数字，而且将输入当作字符并将输入序列当作字符串是很方便的。我们在这里一般会使用这一术语，不过偶尔会将“字符串”简称为“串”。不过，在有些应用中，自动机要转换的输入是从比ASCII字符集更广泛的集合中选出的。例如，编译器可能会把while这样的关键词看作单个输入符号，我们将这种情况用加粗的字符串while表示。因此有时候我们会把这种单独的输入称作“符号”而非“字符”。
10.3.1　确定自动机
在10.2节中讨论过的自动机有个重要的属性。对任意状态s 和任意输入字符x 来说，至多只有一种从状态s 出发的转换的标号中含有x。这样的自动机就称为确定自动机。
为给定输入序列模拟确定自动机是很简单的。在任意状态s 中，给定下一个输入字符x，考虑从s 出发的每种转换的标号。如果我们找到标号含x 的转换，那么该转换就指向适当的下一个状态。如果没有含x 的转换，那么该自动机就“死机”了，而且不能再继续处理输入，就像图10-3中的自动机在到达状态5后就会停机那样，因为它知道自己已经找到了子序列aeiou。
将确定自动机转变为程序是很容易的。我们为每个状态编写一段代码。对应状态s 的代码会检查它的输入，并决定应该遵循从s 出发的哪种转换（如果存在这样的转换）。如果选定了从状态s 到状态t 的转换，那么必须安排表示状态t 的代码接着表示状态s 的代码执行，可能是通过goto语句来实现。
这里我们编写了一个对应图10-4所示反弹过滤器自动机的函数bounce()。变量x是用来从输入中读字符的。状态a、b、c 和d 将分别用标号a、b、c和d来表示，而且要使用标号finis表示程序的结尾，也就是在输入中遇到0和1之外的字符时会到达的地方。
代码如图10-7所示。例如，在状态a 中我们会打印字符0，因为a 是非接受状态。如果输入字符是0，就停留在状态a，而且如果输入字符是1，就进入状态b。
void bounce()
/* 状态 a */
putchar('0');
x = getchar();
if (x == '0') /* transition to state a */
if (x == '1') /* transition to state b */
/* 状态 b */
putchar('0');
x = getchar();
if (x == '0') /* transition to state a */
if (x == '1') /* transition to state c */
/* 状态 c */
putchar('1');
x = getchar();
if (x == '0') /* transition to state d */
if (x == '1') /* transition to state c */
/* 状态 d */
putchar('1');
x = getchar();
if (x == '0') /* transition to state a */
if (x == '1') /* transition to state c */
图 10-7　实现图10-4中确定自动机的函数
在“自动机”的定义中没有要求从某给定状态出发的转换的标号必须是不相交的，如果集合没有相同的成员则说它们是不相交的，即它们的交集为空。如果有图10-8所示的这种图，其中针对输入x 有从状态s 到状态t 和状态u 的转换，这样一来该自动机要如何用程序来实现就不是很清楚了。也就是说，在执行对应状态s 的代码时，如果发现x 是下一个输入字符，就得知接下来一定要进入表示状态t 的代码的开头，而且还要进入表示状态u 的代码的开头。因为程序一次不能到达两个位置，所以要如何模拟从状态出发的转换具有相同标号的自动机是很不明朗的。
图 10-8　从状态s 出发的针对输入x 的非确定转换
10.3.2　非确定自动机
非确定自动机可以具有从某一状态出发的包含相同符号的两个或多个转换，但这不是必须的。请注意，严格地讲，确定自动机也是一种非确定自动机，它只是刚好没有针对同一符号的多种转换。一般来说“自动机”都是不确定的，不过我们在强调自动机不是确定自动机时还是会使用“非确定自动机”的说法。
正如上文提过的，非确定自动机不能直接用程序实现，不过它们对这里将要讨论的若干应用来说是很实用的概念工具。此外，通过利用10.4节中将要介绍的“子集构造”，可以将任意非确定自动机转换成接受相同字符串集合的确定自动机。
10.3.3　非确定自动机的接受
在我们试图模拟针对输入字符串a1a2…ak的非确定自动机时，可能发现同一个字符是多条路径的标号。习惯上讲，如果至少有一条由某输入编辑的路径可以通向接受状态，就可以说非确定自动机接受这一输入字符串。以接受状态结尾的那一条路径，要比任意数量以非接受状态结尾的路径更重要。
不确定性和猜测
认为不确定性让自动机可以“猜测”是种看待不确定性的实用方式。如果我们不知道在某给定状态中要对某给定的输入字符做什么，就可以对下一个状态做出若干选择。因为由带向接受状态的字符串标记的任意路径会被解释为接受，所以非确定自动机其实被赋予了进行一次正确猜测的信用，而不管它还会造成多少次错误猜测。
反性别歧视言论联盟（League Against Sexist Speech，LASS）希望找到含单词man的性别歧视文字。他们不止想捕获ombudsman（特派员）这样的构词，还希望捕获诸如maniac（狂人）或emancipate（解放）这样形式更为微妙的歧视。LASS计划设计一个使用自动机的程序，该程序会扫描字符串，并会在它从输入中任意位置找到字符串man时“接受”该输入。
图 10-9　可识别大多数（而非全部）以man结尾的字符串的确定自动机
大家可能首先会尝试如图10-9所示的确定自动机。在该自动机中，状态0，也就是起始状态，表示的是我们还没看到man这几个字母时的情况。状态1是用来表示我们已经看到m的情形，在状态2中我们已经识别了ma，而在状态3中我们已经看到了man。在状态0、状态1和状态2中，如果我们没有看到想找的字母，就回到状态0并再次尝试。
不过，图10-9并不能很正常地完成处理。在处理command这样的输入时，当它读c和o时会停留在状态0中。在读第一个m时它会进入状态1，不过第二个m又会把它带回状态0，随后它就无法离开状态0了。
可以正确识别内嵌了man的字符串的非确定自动机如图10-10所示。关键的革新在于，我们在状态0中会猜测m是否标志着man的开始。因为该自动机是非确定自动机，它允许同时猜测“是”（由从状态0到状态1的转换表示）和“否”（由可以对包括m在内的所有字母执行从状态0到状态0的转换这一事实表示）。因为非确定自动机的接受需要的不过是一条通向接受状态的路径，所以我们可以受益于这两种猜测。
图 10-10　可识别所有以man结尾的字符串的非确定自动机
图10-11展示了图10-10中的非确定自动机在处理输入字符串command时的行动。在回应c和o时，该自动机只能停留在状态0中。在输入第一个m时，自动机可以选择进入状态0或状态1，因此它同时进入了这两个状态。在处理第二个m时，从状态1是没办法继续行进的，所以该分支就成了一条“死路”。不过，从状态0可以再次进入状态0或状态1，这里又同时进入这两种状态。当输入a时，可以从状态0到达状态0，并从状态1到达状态2。同样，在输入n时，可以从状态0到达状态0，并且从状态2到达状态3。
图 10-11　模拟图10-10中的非确定自动机处理输入串command的情况
因为状态3是接受状态，所以在该点处我们可以接受这一输入。2对接受状态而言，在看到comman后也处在状态0中这一事实是无关紧要的。最后的转化是针对输入d的，从状态0到状态0。请注意状态3不会针对任意输入行进到任何位置，所以该分支也完结了。
2请注意，图10-10中的自动机就像图10-3中的自动机那样，在看到它查找的模式时就会接受，而不是在单词的结尾接受。当我们最终把图10-10转换成确定自动机时，就可以根据它设计能打印整个单词的程序了，就像图10-2中的程序那样。
还要注意，图10-9中展示的用来处理未接收到单词man后一个字符这种情况的回到状态0的转换，在图10-10中是不必要的，因为在图10-10中我们看到输入man时不一定要沿着序列从状态0到状态1再到状态2最后到状态3。因此，虽然状态3看起来“已死”，而且在看到man时已终止计算，但是我们在看到man时也停留在状态0中。该状态允许我们在处理manoman这样的输入时，于读第一个man期间停留在状态1中，并在读第二个man时行经状态1、状态2和状态3，以此来接受manoman这样的输入。
当然，图10-10的设计尽管很动人，但不能直接转换为程序。我们将在10.4节中看到如何把图10-10转换成只含4个状态的确定自动机。与图10-9不同的是，该确定自动机可以正确地识别所有出现man的单词。
尽管可以把任意非确定自动机转换成确定自动机，但并非总是像图10-10所示的情况这般幸运。在图10-10中的情况下，可以看到对应的确定自动机的状态不会多于原非确定自动机的状态，也就是各有4个状态。但事实上，还存在另外一些非确定自动机，与它们对应的确定自动机会含有更多状态。一个含n种状态的非确定自动机有可能只能转换成含2n个状态的确定自动机。下一个示例正好就是确定自动机的状态要比非确定自动机的状态多得多的情况。因此，对同一个问题而言，设计非确定自动机可能比设计确定自动机简单得多。
当本书作者之一Jeffrey D.Ullman之子Peter Ullman上四年级时，他的一位老师试图通过为学生们布置一些“部分换位构词”问题来增加他们的词汇量。该老师每周会给学生们布置一个单词，并要求他们找出使用该单词的一个或多个字母可以构成的所有单词。
有那么一周，该老师布置的单词是Washington，本书的两位作者聚在一起，决定进行一次穷举查找，看看到底可能形成多少个单词。利用/usr/dict/words文件与含3个步骤的过程，我们找到了269个单词，其中有以下5个含7个字母的单词：
因为字母的大小写对本问题来说不重要，所以第一步就是要把词典中所有的大写字母全部转化为小写字母。执行这一任务的程序是很简单的。
第二步是选取只含来自集合S={a，g，h，i，n，o，s，t，w}中的字母（washington中的字母）的单词。图10-12中的确定自动机就能完成该任务。newline字符是/usr/dict/words中标记行尾的字符。如果我们遇到newline之外的其他任意字符，就不用进行转换，而且自动机决不会到达接受状态1。如果在只读到washington中的字母后遇到newline，就进行从状态0到状态1的转换并接受该输入。
图 10-12　检测由washington中出现的字母所构成单词的自动机
图10-12中的自动机接受hash这样的单词，也就是相应字母出现的次数多于washington本身中字母出现次数的单词。因此，我们的第三步也是最后一步就是，排除那些包含3个或更多n，或是包含两个或更多S中其他字符的单词。这一任务也可以由自动机来完成。例如，图10-13中的自动机接受的是至少有两个a的单词。我们会停留在状态0中，直至看到a，在这种情况下就进入状态1。接着会保持状态1，直到看到第二个a，才进入状态2并接受该输入。该自动机接受那些因为有太多a而不能用washington部分换位构词得到的单词。在这种情况下，我们想要的刚好是那些在处理过程中从不会让自动机进入接受状态2的单词。
图 10-13　如果输入存在两个a就接受该输入的自动机
图10-13所示的自动机是确定自动机。不过，它只表示了某单词可被图10-12中的自动机接受却仍不是washington经部分换位构词得到的单词的9种原因之一。要接受具有washington中某个字母太多实例的全部单词，我们可以使用图10-14中的非确定自动机。
图10-14从状态0中开始，而且它针对任意字母的一种选择就是留在状态0中。如果输入字符是washington中的任意一个字母，就有另一种选择；该自动机还会猜测它应该转换到这样一个状态，该状态的功能是记住该字母已经出现过一次。例如，针对字母i，我们有进入状态7的选择。然后我们就会留在状态7中，直到看到另一个i，从而进入作为接受状态之一的状态8。回想一下，在该自动机中，接受就意味着输入字符串不是由washington经过部分换位构词得到的单词，在这里描述的情况中就是因为该单词含有两个i。
因为在washington中有两个n，所以对n的处理有些不同。自动机在看到一个n后会进入状态9，而在看到第二个n后会进入状态10，接着在看到第三个n时才进入接受状态11。
图 10-14　检测含有一个以上的a、g、h、i、o、s、t或w，或者两个以上n的单词的非确定自动机
例如，图10-15展示了读输入字符串shining之后的所有状态。因为我们在读第二个i后会进入接受状态8，所以shining不是由washington经过部分换位构词得到的单词，即便它因为只含有washington中可以找到的字母而能被图10-12中的自动机接受。
图 10-15　图10-14中的非确定自动机处理输入字符串shining时进入的状态
总结下来，我们的算法由以下3步组成。
(1) 首先将词典中的所有大写字母转换成小写字母。
(2) 找到10-12中的自动机接受的所有单词，这些单词只由washington中的字母组成。
(3) 从步骤(2)得到的单词中删除图10-14中非确定自动机接受的所有单词。
该算法是在/usr/dict/words文件中找到可由Washington经过部分换位构词得到的单词的简单方法。当然，必须找到某种合理的方式来模拟图10-14中的非确定自动机，我们将在10.4 中讨论如何完成这一任务。
10.3.4　习题
1. 编写C语言程序，实现图10-9中确定自动机的算法。
2. 设计确定自动机，使其能正确地找出字符串中出现的所有子字符串man。并将该自动机实现为程序。
3. LASS希望检测出所有含字符串man、son和father的单词。设计非确定自动机，使其只要找到这3个字符串中任意一个就接受相应的输入字符串。
4. * 设计确定自动机，使其可以解决习题(3)中的问题。
5. 模拟图10-9和图10-10中的自动机处理字符串summand时的情况。
6. 模拟图10-14的自动机处理以下字符串的情况。
(b) antagonist
(c) hashish
其中哪些字符串会被接受？
7. 可以用具有状态、输入和接下来这些属性的关系来表示自动机。这样做的目的是，如果(s，x，t )是个元组，那么输入符号x 就是从状态s 到状态t 的转换的标号。如果该自动机是确定自动机，那么该关系合适的键是什么？如果该自动机是非确定自动机呢？
8. 如果只是想在给定某状态和某输入符号的情况下找出接下来的（一个或一些）状态，大家会建议用什么数据结构来表示习题(7)中的关系？
9. 将如下图所示的自动机表示为关系。
(a) 图10-10
(b) 图10-9
(c) 图10-14
可以使用椭圆来表示Λ-m 这样针对含大量字母的集合的转换。
不编程找到部分换位构词形成的单词
顺便提一句，我们可以使用UNIX系统的命令，几乎不进行编程就实现示例10.6中的3步算法。对步骤(1)，可以使用UNIX命令
tr A-Z a-z &/usr/dict/words　　　　　　(10.1)
把大写字母转化成小写字母。对步骤(2)，可以使用命令
egrep '^[aghinostw]*$'　　　　　　(10.2)
粗略地讲，就是定义了图10-12中那样的自动机。对步骤(3)，可以使用命令
egrep -v 'a.*a|g.*g|h.*h|i.*i|n.*n.*n|o.*o|s.*s|t.*t|w.*w'　　　　　　(10.3)
该命令指定了类似图10-14中自动机的事物。整个任务可以使用以下三元素管道来完成：
(10.1) | (10.2) | (10.3)
也就是说，整个命令是通过用表示各行的文本替换各行形成的。竖线，或者说“管道”符号，使得左侧命令的输出可以成为右侧命令的输入。我们将在10.6节中讨论egrep命令。
10.4　从不确定到确定
在本节中我们将会看到，每一个非确定自动机都可以被确定自动机替代。正如我们已经看到的，在执行某些任务时，考虑非确定自动机有时要更简单些。不过，因为根据不确定自动机编写程序不如根据确定自动机编程那样容易，所以找到一种将不确定自动机变形为等价的确定自动机的算法是很重要的。
10.4.1　自动机的等价性
在10.3节中，我们已经看到两种接受观。在某些示例中，比如在示例10.1（含有子序列aeiou的单词）中，接受就意味着整个单词被接受，即便我们可能没有扫描完整个单词。而在另一些例子中，比方说示例10.2的反弹过滤器中，或是图10-12所示的自动机（字母全在washington中的单词）中，只有在我们想对从启动自动机以来已经看到的确切输入表示认可时才接受该输入。因此，在示例10.2中，我们接受所有能带来输出1的输入序列。在图10-12中，只有在已经看到newline字符，知道已经看到整个单词时才接受该输入。
当谈论正式的自动机行为时，我们只需要第二种解释（当前的输入被接受）。严格地讲，假设A 和B 是两个自动机（确定或不确定）。如果A 和B 接受相同的输入字符串集合，就说它们是等价的。换句话说，如果a1a2…ak 是任意符号串，那么以下两个条件是成立的。
1. 如果从A 的起始状态到A 的某个接受状态存在以a1a2…ak 标记的路径，那么从B 的起始状态到B 的某个接受状态也存在以a1a2…ak 标记的路径。
2. 如果从B 的起始状态到B 的某个接受状态存在以a1a2…ak 标记的路径，那么从A 的起始状态到A 的某个接受状态也存在以a1a2…ak 标记的路径。
考虑图10-9和图10-10中的自动机。正如我们在图10-11中注意到的，图10-10中的自动机接
受输入字符串comman，因为该字符序列在图10-10中标记了路径0→0→0→0→1→2→3，而且这一路径是从起始状态出发，到达了一个接受状态。不过，在图10-9所示的确定自动机中，可以验证由comman标记的路径只有0→0→0→1→0→0→0。因此如果图10-9是自动机A，而图10-10是自动机B，就违背了上述第(2)点，这样就表明这两个自动机不是等价的。
10.4.2　子集构造
我们现在将会看到，如何通过构造等价的确定自动机来“消除自动机的不确定性”。这一技巧叫作子集构造，而且它的本质就如图10-11和图10-15所示，在这两幅图中我们模拟了处理特殊输入的非确定自动机。从这两幅图中我们注意到，在任何给定的时间，非确定自动机都在某一状态集合中，而且这些状态都出现在模拟图的同一列中。也就是说，在读了某输入列a1a2…ak 之后，非确定自动机就“在”那些从起始状态出发沿着标记有a1a2…ak 的路径可以到达的状态中。
在读完输入字符串shin之后，图10-15所示的自动机处在状态集合{0，5，7，9，14}中。这些状态都出现在第一个n后的一列中。在读下一个i后，它处在状态集合{0，5，7，8，9，14}中，而在读了接下来的n后，在状态集合{0，5，7，9，10，14}中。
现在就有了如何把非确定自动机N 转换为确定自动机D 的线索。D 的状态各自是N 的状态的集合，而且D 中状态间的转换是由N 的转换确定的。要看到如何构建D 的转换，设S 是D 的某个状态，而且x 是某输入符号。因为S 是D 的状态，所以它是由N 的状态组成的。定义集合T 是自动机N 中那些状态t，这些状态满足存在S 中的状态s，以及自动机N 针对包含输入符号x 的集合的从s 到t 的转换。那么在自动机D 中我们就放置一个在针对符号x 的从S 到T 的转换。
示例10.8展示了多个针对输入符号的从一个确定状态到另一个确定状态的转换。在当前的确定状态是{0，5，7，9，14}，而且输入符号是字母i时，我们在该示例中看到，根据图10-14中的非确定自动机，接下来的不确定状态集是T={0，5，7，8，9，14}。由针对输入符号n 的这一确定状态可知，接下来的不确定状态集是U={0，5，7，9，10，14}。这两个确定转换如图10-16所描述的那样。
图 10-16　确定状态S、T 和U 之间的转换
现在我们知道该如何在确定自动机D 的两个状态之间构建转换了，不过需要确定自动机D 确切的状态集、D 的起始状态，以及D 的接受状态。我们要用归纳法来构建D 的状态。
依据。如果非确定自动机N 的起始状态是s0，那么确定自动机D 的起始状态是{s0}，也就是只含s0这一个元素的集合。
归纳。假设已经确定了N 的状态集S 是D 的一个状态。依次考虑每个可能的输入字符x。对某个给定的x，设T 是N 的状态t 构成的集合，其中状态t 满足对S 中的某个状态s 而言，存在标号含x 的从s 到t 的转换。那么集合T 就是D 的一个状态，而且存在针对输入x 的从S 到T 的转换。
D 的接受状态是N 的状态集中至少包含N 的一个接受状态的。这从直觉上讲是说得通的。如果S 是D 的状态而且是N 的状态集，那么能把D 从其起始状态带到状态S 的输入a1a2…ak 也能把N 从其起始状态带到S 中的所有状态。如果S 含有某个接受状态，那么a1a2…ak 会被N 接受，而且D 也一定会接受该输入。因为D 在接收输入a1a2…ak 时只会进入状态S，所以S 肯定是D 的接受状态。
图 10-17　识别以man结尾字符串的非确定自动机
图10-17重现了图10-10所示的非确定自动机，我们来把它转换成确定自动机D。先从D的起始状态{0}开始。
这一构建过程的归纳部分要求我们查看D 的每个状态，并确定它的转换。对{0}而言，只需要询问状态0通向哪里。分析图10-17得到的答案是，对除了m之外的任意字母，状态0只能进入状态0，而对输入m，它同时通向状态0和状态1。因此自动机D 需要已经具备的状态{0}和我们必须添加的状态{0，1}。目前为止已经为D 构建的转换和状态如图10-18所示。
图 10-18　状态{0}及其转换
接下来，必须考虑从状态{0，1}出发的转换。再次研究图10-17，我们看到，对除了m和a之外的所有输入，状态0只通向状态0，而状态1则不能通向任何地方。因此，存在从状态{0，1}到状态{0}的转换，标记为除了m和a之外的所有字母。对输入m，状态1还是不能通向任何地方，不过状态0会同时通向状态0和状态1。因此，存在从状态{0，1}到其本身的转换，标记为m。最后，对输入a，状态0只会通向它自己，不过状态1是通向状态2的。因此存在标记为a的从状态{0，1}到状态{0，2}的转换。目前为止D 已经构建起的部分如图10-19所示。
图 10-19　状态{0}和{0，1}，以及它们的转换
现在需要构建从状态{0，2}出发的转换。对除m和n之外的所有输入，状态0只能通向状态0，而状态2则哪里都去不了，因此存在从{0，2}到{0}的转换，标记为除了m和n之外的所有字母。对输入m，状态2不通向任何状态，而状态0则同时通向状态0和状态1，因此标记为m的从状态{0，2}到状态{0，1}的转换。对输入n，状态0只通向它本身，而状态2会通向状态3。因此存在标记为n的从状态{0，2}到状态{0，3}的转换。D的该状态是接受状态，因为它包含了图10-17中的接受状态——状态3。
最后，必须给出从状态{0，3}出发的转换。因为对任何输入，状态3都不通向任何状态，从状态{0，3}出发的转换只反映从状态0出发的转换，因此会与{0}通向相同的状态。因为从状态{0，3}出发的转换不会将我们带到尚未见过的D的状态，所以对D的构造就完成了。完整的确定自动机如图10-20所示。
图 10-20　确定自动机D
请注意，这一确定自动机可以正确地接受所有以man结尾的字母串，而且只接受以man结尾的字母串。直觉上讲，只要字符串目前为止不是以m、ma、man结尾，该自动机就会处在状态{0}中。状态{0，1}意味着目前为止看到的字符串是以m结尾的，状态{0，2}表示当前的字符串是以ma结尾，而状态{0，3}则说明当前字符串的结尾为man。
示例 10.10
图10-17中的非确定自动机有4个状态，而图10-20中与它等价的确定自动机也有4个状态。如果所有的非确定自动机都能转换成小型确定自动机就好了，例如，在编译编程语言中常用到的某些自动机其实可以转换成相当小的确定自动机。不过，不能保证确定自动机一定很小，具有k个状态的非确定自动机有可能最终被转换成状态多达2k 个的确定自动机。也就是说，对非确定自动机状态集的幂集中的每个成员，确定自动机都有相应的状态。
举个会得到很多状态的例子，考虑一下10.3节图10-14中的自动机。因为该非确定自动机有20种状态，可以想象一下，通过子集构造构建的确定自动机可能有约220个，或者说是超过100万个状态，这些状态全都是{0,1,…,19}的幂集的成员。实际结果并没有这么糟，但也存在相当多的状态。
我们不会尝试画出与图10-14中非确定自动机等价的确定自动机。不过，可以考虑一下实际上需要哪些状态集。首先，因为对每个字母都有从状态0到其自身的转换，所以实际看到的所有状态集都包含0。如果字母a尚未输入，就不能到达状态1。不过，如果刚好已经看到一个a，不管还看到些什么，我们都将在状态1中。我们还可以为washington中其他任何字母得出相似的论断。
如果在状态0中开始图10-14，并为其提供属于washington中所出现字母的子集的一列字母，然后除了在状态0中之外，还可以在状态1、3、5、7、9、12、14、16和18的某个子集中。通过恰当地选择输入字母，我们可以安排在这些状态集的任意一个中。因为有29=512个这样的集合，所以在与图10-14等价的确定自动机中至少有这么多个状态。
不过，其中的状态要更多，因为字母n在图10-14中得到了特殊处理。如果在状态9中，我们还可以在状态10中，而且如果已经看到两个n，其实就将同处状态9和状态10中。因此，尽管对其他8个字母来说都只有两个选择（比如，对字母a，要包含状态1，要么不含状态1），而对字母n来说，共有3种选择（既不含状态9也不含状态10、只包含状态9，或者同时包含状态9和状态10）。因为至少存在3×28=768种状态。
不过这并非全部。如果到目前为止的输入以washington中的字母之一结束，而且我们之前已经看到足够多的该字母，那么我们也应该在对应该字母的接受状态中，比方说，对a来说就是状态2。然而，我们在处理相同输入后不可能在两个接受状态中。为增加的状态集计数变得更麻烦了。
假设接受状态2是该集合的成员。那么可知1也是该集合的成员，0当然也是，不过我们仍然对与除a之外的字母对应的状态拥有所有选择，这类集合的数量是3×27，或者说是384。如果我们的集合包含接受状态4、6、8、13、15、17或19，这样的道理也同样实用，在每种情况中都有384个集合包含相应的接受状态。唯一的例外就是含接受状态11（就是状态9和状态10也出现）的情况。在该情况下，只有28＝256种选择。因此，该等价确定自动机的状态总数为：
768+8×384+256＝4864
第一项768表示那些不含接受状态的集合的数量。接下来的一项，表示的是分别包含与除n之外其他8个字母对应的接受状态的8类集合的数量，第三项256则表示含状态11的集合的数量。
关于子集构造的想法
子集构造是相当不好理解的。特别是确定自动机的状态可以是非确定自动机的状态集这一思路可能需要大家耐心思考才能想通。不过，这种把结构化对象（状态集）与原子对象（确定自动机的各个状态）融合成同一对象的概念，是计算机科学中的一种重要概念。我们已经在程序中看到过这一概念，而且经常必须用到它。例如，函数的参数，比方说L，表面上看是原子的，而对其进行更仔细的检查可能发现它是有着复杂结构的对象，比如，具有连接到其他记录的字段从而能形成表的记录。同样，图10-20中确定自动机D 的状态{0，2}也可以用简单的名称“5”或“a”来代替。
10.4.3　子集构造起效的原因
很明显，如果D 是利用子集构造从非确定自动机N 构建的，那么D 就是确定自动机。原因在于，对每个输入符号x 和D 的每个状态S 而言，我们定义了D 的某特定状态T，它满足从S 到T 的转换的标号中包含x。不过如何得知自动机N 和D 是等价的呢？也就是说，我们需要知道，对任意输入序列a1a2…ak，当且仅当N 接受a1a2…ak 时，在下列情况下，自动机D 到达的状态S 是种接受状态。
1. 从起始状态开始；
2. 并且沿着标记为a1a2…ak 的路径行进。
请记住，当且仅当从N 的起始状态有一条标记为a1a2…ak 的路径能到达N 的某个接受状态时，N 才会接受a1a2…ak。
D 所做的事情与N 所做的事情之间的联系就更紧密了。如果D 具有从它的起始状态到标记为a1a2…ak 的状态的路径，那么被视为自动机N 的某个状态集的集合S，就刚好是从N 的起始状态开始沿着某标记为a1a2…ak 的路径所能到达的状态组成的集合。这种关系如图10-21所示。因为我们已经定义了，只有在S中的某一成员是N 的接受状态时，S才是D的接受状态，所以要得出D和N都接受a1a2…ak 或都不接受a1a2…ak，也就是要得出D 和N 是等价的，就只需要图10-21所示的关系。
图 10-21　非确定自动机N 的操作与对应的确定自动机D 的操作间存在的关系
我们需要证明图10-21所示的关系，该证明要对输入字符串长度k 进行归纳。需要通过对k 的归纳来证明的正式命题是，从D 的起始状态开始沿着标记为a1a2…ak 的路径到达的状态{s1，s2，…，sn}，刚好是从N 的起始状态开始沿着标记为a1a2…ak 的路径到达的状态构成的集合。
依据。设k=0。长度为0的路径将我们留在出发的位置，也就是，在自动机D 和N 的起始状态中。回想一下，如果s0是N 的起始状态，D 的起始状态就是{s0}。因此该归纳命题对k=0来说成立。
归纳。假设该命题对k成立，并考虑输入字符串a1a2…akak+1。那么标记为a1a2…akak+1的从D的起始状态到状态T的路径就如图10-22所示，也就是说，在它针对输入ak+1进行到T的转换（最后一次转换）之前，会经过某个状态S。
图 10-22　S 是D 在到达状态T 之前到达的状态
通过归纳假设，可以假设S 正好是自动机N 从其起始状态沿着标记为a1a2…ak 的路径所能到达的状态组成的集合，并必须证明T 刚好是从N 的起始状态出发沿着标记为a1a2…akak+1的路径所能到达的状态组成的集合。该归纳步骤的证明包含下列两个部分。
(1) 必须证明，T不含过多的状态，也就是说，如果t是在T中的N的状态，那么t是从N的起始状态沿着标记为a1a2…akak+1的路径可以到达的。
(2) 必须证明，T包含足够的状态，也就是说，如果t是从N的起始状态沿着标记为a1a2…akak+1的路径可以到达的状态，那么t就在T中。
对(1)来说，设t 在T 中。那么，如图10-23所示，在S 中一定存在一个状态s，可以证实t 在T 中。也就是说，在N 中存在从s 到t 的转换，而且它的标号包含ak+1。根据归纳假设，因为s 在S 中，所以肯定存在从N 的起始状态到s 的标记为a1a2…ak 的路径。因此，存在从N 的起始状态到t，标记为a1a2…akak+1的路径。
图 10-23　S 中的状态s 解释了为何将状态t 放进T 中
现在必须证实(2)，也就是如果存在从N 的起始状态到t 的，标记为a1a2…akak+1的路径，那么t 就在T 中。就在这条路径针对输入ak+1进行到t 的转换之前，肯定会经过某个状态s。因此，存在从N 的起始状态开始到s，标记为a1a2…ak 的路径。根据归纳假设，s 在状态集S 中。因为N 具有从s 到t 而且标号含有ak+1的转换，所以应用到状态集S 和输入符号ak+1上的子集构造需要t 被放置到T 中。因此t 在T 中。
在给定归纳假设的情况下，现在就证明了，T 刚好是由N 中从N 的起始状态开始沿着标记为a1a2…akak+1的路径可达的状态组成的。这就是归纳步骤，因此可以得出，沿着标记为a1a2…ak 的路径到达的确定状态机D 的状态，永远都是N 沿着标号相同的路径可达的状态组成的集合。因为D 的接受状态是那些包含N 的某个接受状态的状态集，所以可以得到D 和N 接受相同字符串的结论，也就是说D 和N 是等价的，所以子集构造是“行得通的”。
10.4.4　习题
1. 利用子集构造，把10.3节习题3中的非确定自动机转换成确定自动机。
2. 图10-24a到图10-24d中的非确定自动机可以识别什么模式？
3. 把图10-24a到图10-24d中的非确定自动机转换成确定有限自动机。
自动机的最小化
与自动机相关，特别是在利用自动机设计电路时会遇到的一个问题就是，执行某给定任务需要多少状态。也就是说，我们可能要问，给定某自动机，是否存在状态更少的等价自动机?如果这样的话，那么这样的等价自动机中最小的状态数量是多少？
事实证明，如果将问题限制在确定自动机的范畴，那么与任意给定自动机等价的最小状态确定自动机是唯一的，而且很容易找到它。关键就在于定义确定状态机两个状态s 和t 什么时候是等价的，也就是说，对任意的输入序列，分别从s 和t 出发而且由该序列标记的路径，要么都能到达接受状态，要么都不能到达。如果状态s 和t 是等价的，就没法通过为自动机提供输入来区分这两者，因此就可以把s 和t 合并为一个状态。事实上，按照如下方式定义不等价的状态要更容易。
依据。如果s 是接受状态而t 是不接受，那么s 和t 是不等价的，反之亦然。
归纳。如果存在某输入符号x，使得针对输入x 存在从状态s 和t 分别到两个已知状态的转换不等价，那么s 和t 就是不等价的。
要让这个测试起效，还需要补充一些细节。特别要提的是，我们可能必须添加一个“停滞状态”，它不接受任何输入，而且针对所有输入都存在到它自身的转换。由于确定自动机可能针对某个给定符号不存在从某给定状态出发的转换，因此在执行这一最小化程序之前，需要针对所有不存在其他转换的输入，添加从任意状态到该停滞状态的转换。可以注意到，不存在类似的用于最小化非确定自动机的理论。
4. * 某些自动机具有一些根本不存在转换的“状态-输入”组合。如果状态s 不存在针对符号x 的转换，我们就可以添加一种针对符号x 的、从s 到某个特殊的“停滞状态”的转换。停滞状态是不接受状态，而且针对任意输入符号都有到其自身的转换。证明，添加了“停滞状态”的自动机与原有的自动机是等价的。
5. 证明，如果为确定自动机添加了停滞状态，就可以得到具有从起始状态出发而且标记为每个可能字符串的路径的等价自动机。
6. * 证明，如果对确定自动机进行子集构造，那么要么得到相同的自动机，其中每个状态s 都重命名为{s }，要么添加了停滞状态（对应空状态集）。
7. ** 假设有某确定自动机，并要把每个接受状态变成不接受状态，还要把每个不接受状态变成接受状态。
(a) 如何用旧自动机的语言来描述新自动机接受的语言？
(b) 如果先为原自动机加上停滞状态，重复(a)小题。
(c) 如果原自动机是非确定自动机，重复(a)小题。
图 10-24　非确定自动机
10.5　正则表达式
自动机定义了模式，即表示自动机的图中，作为从起始状态到某个接受状态的路径标号的字符串组成的集合。在本节中，我们遇到了正则表达式这种用来定义模式的代数方法。正则表达式与我们熟悉的算术表达式代数，以及第8章中遇到的关系代数都是相似的。有趣的是，可以用正则表达式代数表示的模式组成的集合，刚好与可以用自动机描述的模式组成的集合相同。
表示方式的约定
我们还将继续使用等宽字体来表示出现在字符串中的字符。与某给定字符对应的正则表达式原子操作数则会用加粗的该字符来表示。例如，a是对应字符a的正则表达式。在我们需要使用变量时，会把它写为斜体。变量在这里用来代表复杂的表达式。例如，使用变量letter 表示“任意字母”这个我们很快就要看到其正则表达式的集合。
10.5.1　正则表达式的操作数
与所有的代数一样，正则表达式也具有某几类原子操作数。在算术代数中，原子操作数是常数（比如整数或实数），或可能的值是常数的变量；而对关系代数而言，原子操作数要么是固定的关系，要么是可能的值为关系的变量。在正则表达式代数中，原子操作数是如下几种中的一种。
2. ε 符号；
3. ?符号；
4. 值可能为由正则表达式定义的任意模式的变量。
10.5.2　正则表达式的值
任意代数中的表达式都具有某一类型的值。对算术表达式来说，值可以是整数、实数，或是我们可以处理的任意类型的数字。对关系代数而言，表达式的值就是个关系。
对正则表达式来说，每个表达式的值都是由通常被称为语言的字符串集合组成的模式。由正则表达式E 表示的语言就被称为L(E )，或者是“E 的语言”。原子操作数的语言有如下定义。
1. 如果x是任意字符，那么正则表达式x表示语言{x}；也就是说，L(x)={x}。请注意，该语言是包含一个字符串的集合，该字符串的长度为1，而且字符串中唯一的位置被字符x占据。
2. L(ε )={ε }。作为正则表达式的特殊字符ε 表示只含一个空字符串（或者说长度为0的字符串）的字符串集合。
3. L(?)={?}。作为正则表达式的特殊字符?表示字符串集合为空。
请注意，我们没有定义原子操作数为变量时的值。只有在将变量替换为具体的表达式时，才可以为这样的操作数取值，而且它的值就是相应的表达式的值。
10.5.3　正则表达式的运算
正则表达式中运算符共有3种。这些运算符都可以用括号分组，就像我们所熟悉的代数中那样。和代数表达式中所做的一样，存在一些让我们可以忽略某些括号对的优先次序和结合律。在探讨完这些运算后，我们将会描述关于括号的规则。
第一种，也是我们最熟悉的一种运算符就是并运算符，我们要将其表示为 | 。3为正则表达式取并的规则是，如果R 和S 为两个正则表达式，那么R |S表示R 和S 所表示的语言取并。也就是说，L(R |S )=L(R )∪L(S )。回想一下，L(R )和L(R )都是字符串的集合，所以为它们取并的概念是说得通的。
3在正则表达式中，加号+也常用作并运算符，不过在这里并不这样表示。
示例 10.11
我们知道a是表示{a}的正则表达式，而b是表示{b}的正则表达式。因此a|b就是表示{a，b}的正则表达式。这是一个包含a和b这两个长度为1的字符串的集合，同样，可以写出诸如(a|b)|c这样的表达式，来表示集合{a，b，c}。因为取并是一种有结合性的运算符，也就是说，在为3个集合求并集时，以任意次序组合这些操作数都是没关系的，可以忽略括号，并直接将表达式写为a|b|c。
正则表达式代数的第二个运算符叫作串接（concatenation）。它是用没有任何运算符符号来表示的，就像在写乘法表达式时有时会省略运算符那样，例如，算术表达式ab 就表示a 和b 的积。和取并运算一样，串接运算也是二元的中缀运算符。如果R 和S 是正则表达式，那么RS 就是R 和S 的串接。4
4严格地讲，应该把RS 写为(R )(S )，以强调R 和S 是分开的表达式，因为优先级规则，它们各自的组成部分一定不能混合在一起。这种情况与我们将表达式w+x 与y+z 相乘时类似，一定要将积写为(w+x)(y+z)。请注意，因为乘法要先于加法计算，所以如果把括号去掉，得到的表达式w+xy+z 就不能解释为w+x 与y+z 的积了。正如我们将要看到的，串接与取并具有的优先关系使得它们分别类似与乘法和加法。
RS 表示的语言L(RS )是由语言L(R )和L(S )按照以下方式形成的。对L(R )中的各字符串r 以及L(S )中的各字符串s 来说，字符串r 和s 的串接rs 是在L(RS )中的。回想一下两个表（比如字符串）的串接，是通过按次序取第一个表中的元素，并在它们之后按次序接上第二个表的元素而形成的。
类型之间的一些微妙区别
读者不应该弄混看似相似，实则差别巨大的多种对象。例如，空字符串ε就和空集?不同，而这两者又都与只包含空字符串的集合{ε }不同。空字符串的类型是“字符串”或“字符表”，而空集和只含空字符串的集合都是“字符串集合”类型的。
我们还应该记得类型为“字符”的字符a，类型为“字符串”的长度为1的字符串a，以及类型为“字符串集合”的正则表达式a的值{a}之间的区别。还要注意到在其他的上下文中，{a}可能表示包含字符a的集合，而且我们没有表示方式上的约定用来区分{a}的这两种含义。不过，在本章的内容中，{a}通常都具有前一种解释，也就是“字符串集合”而非“字符集合”。
示例 10.12
设R是正则表达式a，因此L(R)就是集合{a}。再设S是正则表达式b，所以L(S)＝{b}。那么RS就是表达式ab。要形成L(RS)，需要取L(R)中的每个字符串，将其与L(S)中的每个字符串串接。在这种简单的情况中，L(R)和L(S)都是单元素集，所以对其二者来说都各自只有一种选择。我们从L(R)中选择a，并从L(S)中选择b，然后将这两个长度为1的表串接起来，就得到了字符串ab。因此L(RS)就是{ab}。
可以对示例10.12进行概括，得出任意用粗体表示的字符串，都是表示由一个字符串（相应字符组成的表）构成的语言的正则表达式。比如，then就是语言为{then}的正则表达式。我们将看到，串接是一种具有结合性的运算符，所以不管正则表达式中的字符如何分组都是没关系的，而且不需要使用括号。
示例 10.13
现在来看看两个语言不是单元素集的正则表达式的串接。设R是正则表达式a|(ab)。5语言L(R )就是L(a)和L(ab)的并集，即{a，ab}。设S是正则表达式c|(cb)。同样，L(S )={c，cb}。正则表达式RS 就是(a|(ab))(c|(cb))。请注意，出于运算优先级的原因，R 和S 上的括号是必要的。
5正如接下来将要看到的，串接要优先于取并，所以这里的括号是多余的。
图 10-25　形成{a，ab}和{c，cb}的串接
要找出L(RS )中的字符串，就要将L(R )中的两个字符串与L(S )中的两个字符串一一配对。这一配对方式如图10-25所示。从L(R )中的a和L(S )中的c，可以得到字符串ac。而字符串abc可以用两种不同方式得到，要么是(a)(bc)，要么是(ab)(c)。最后，L(R )中的ab与L(S )中的bc串接就得到字符串abbc。因此L(RS )就是{ac，abc，abbc}。
请注意，语言L(RS )中的字符串数量不可能大于L(R )中字符串数量和L(S )中字符串数量的积。事实上，L(RS )中字符串的数量刚好就是这个积，除非存在一些“巧合”，也就是同一字符串可以通过两种或多种不同方式形成的情况。示例10.13就是这样一个例子，其中字符串abc就可以用两种方式生成，因此L(RS )中就只有3个字符串，要比R 和S 的语言中字符串数量之积少1。同样，语言L(R | S )中字符串的数量也不大于语言L(R )和L(S )中字符串数量的和，而且在L(R )和L(S)中有相同字符串时只可能比该和小。在讨论这些运算符的代数法则时我们还将看到，正则表达式的取并和串接，与算术运算符+和×之间，存在一种相近但不精确的类比。
第三个运算符是克林闭包（Kleene closure）或直接称为闭包。6它是个一元的后缀运算符，也就是说，它接受一个操作数并且出现在该操作数之后。闭包是用星号表示的，所以R *是正则表达式R 的闭包。因为闭包运算符有着最高的优先级，所以通常需要在R 两侧放上括号，将其写为(R )*。
6StevenC.Kleene最早撰写了描述正则表达式代数的论文。
闭包运算符的作用是表示“R 中的字符串没有出现或多次出现”。也就是说，L(R *)由下列内容组成。
1. 空字符串ε，可以将其视作R 中的字符串没有出现。
2. 在L(R )中的所有字符串，表示L(R )中的字符串出现一次。
3. 在L(RR )中的所有字符串，也就是L(R )与自身的串接，表示L(R )中的字符串出现两次。
4. 在L(RRR )、L(RRRR )等中的所有字符串，表示L(R )中的字符串出现3次、4次和更多次。可以有如下非正式的表示
R *＝ε | R |RR |RRR |…
不过，一定要理解，等号右侧的表达式并不是正则表达式，因为它包含无数个取并运算符。而所有正则表达式都是用有限数量的这3种运算符构建的。
示例 10.14
设R=a。那么L(R *)是什么？当然，ε 肯定在该语言中，因为它一定在任意闭包中。而L(R )中唯一的字符串a也在该语言中，还有L(RR )中的aa，L(RRR )中的aaa，等等。也就是说，L(a*)是由含0个或多个a的字符串组成的集合，也就是{ε，a，aa，aaa，…}。
示例 10.15
现在设R是正则表达式a|b，那么L(R )={a，b}，并考虑L(R *)是什么。该语言还是含有ε，表示L(R )中字符串没有出现。R中的字符串出现一次就为L(R *)带来了{a，b}。出现两次就给我们4个字符串{aa，ab，ba，bb}，3次出现就给了我们由a和（或）b组成长度为3的8个字符串，以此类推。因此L(R *)是所有由a和（或）b组成的任意有限长度的字符串。
10.5.4　正则表达式运算符的优先级
正如我们在前面的内容中非正式提到的，正则表达式的3个运算符并、串接和闭包之间存在约定的优先级次序。这一次序如下。
1. 闭包（最高）；
2. 然后是串接；
3. 然后是并（最低）。
因此，在解释任何正则表达式时，首先要为闭包运算符分组，也就是找出具有表达式形式（即如果存在括号的话，则它们是配对的）的紧邻某给定*左侧的最短表达式。可以给该表达式和相应的*加上一对括号。
接下来，要从左边起考虑串接运算符。对每个串接运算符，要找到紧邻其左侧的最小表达式并找到紧邻其右侧的最小表达式，再给这一对表达式加上括号。最后，要从左侧起考虑取并运算符。找到紧邻每个取并运算符左右的表达式，并这这一对中间有着取并符号的表达式周围加上括号。
示例 10.16
考虑表达式a|bc*d。首先分析*。该表达式中只有一个*，而且在其左侧的最小表达式为c。因此可以把该*与他的操作数分到一组，就成了a|b(c*)d。
接下来，要考虑上述表达式中的串接。共有两次串接，一次是b和左括号之间的，另一次是在右括号和d之间的。首先分析第一次串接，我们看到b就是紧邻左侧的，而到右侧就必须到将右括号包括在内为止，因为表达式的括号必须是平衡的。因此，第一次串接的操作数分别是b和(c*)。给它们周围加上括号就得到表达式
a|(b(c*))d
对第二次串接来说，紧邻其左的最短表达式现在是(b(c*))，而紧邻其右的最短表达式是d。在给这次串接的操作数分组加上括号后，表达式就成了
a|((b(c*))d)
最后，必须考虑取并运算。该表达式中总共有一次取并运算，它的左操作数为a，而其右操作数就是上述表达式其余的部分。严格来说，必须为整个表达式再加上一层括号，得到
(a|(b(c*)d))
不过最外层的括号是多余的。
10.5.5　正则表达式的其他一些示例
在本节最后，我们要给出一些更复杂的正则表达式。
示例 10.17
可以将示例10.15中的思路扩展到“由符号a1、a2、…、an 组成的任意长度的字符串”以及如下正则表达式：
(a1|a2|…|an)*
例如，可以按照以下方式描述C语言标识符。首先，定义正则表达式：
letter=A|B|…|Z|a|b|…|z|_
这就是说，C语言中的“字母”包括大小写英文字母和下划线。同样，我们还定义了正则表达式：
digit = 0|1|… | 9
那么正则表达式
letter(letter|digit)*
就表示由字母、数字和下划线组成的所有不以数字开头的字符串。
示例 10.18
现在来考虑一个更难写出的正则表达式：在示例10.2中讨论过的反弹过滤器问题。回想一下，我们描述了这样一种自动机，粗略地讲，就是只要输入的结尾是一列1，就会输出1。也就是说，只要在一行中看到两个1，就认为我们已经在一列1中，不过在确定看到的是一列1后，一个0的出现并不会让我们推翻这一结论。因此，每当输入的结尾有由两个1组成的序列时，只要它后面跟上的内容中每个0之后要么立即跟上一个1，要么是当前为止看到的最后一个输入字符，示例10.2中自动机的输出就是1。可以用如下正则表达式表示这种情况。
(0|1)*11(1|01)*(ε|0)
要理解该正则表达式，首先要注意到(0|1)*表示由0和1组成的任意字符串。这些字符串后面一定要跟上两个1，就如表达式11所表示的。因此(0|1)*11就是所有由0和1组成且结尾（至少）有两个1的字符串。
接下来(0|01)*表示所有由0和1组成，而且其中所有0后面都跟着1的字符串。也就是，该表达式语言中的字符串是以任意次序串接任意数量的字符串1和01构成的。尽管1让我们在任意时刻都可以向正在形成的字符串添加一个1，不过01强迫我们在任何0之后都加上一个1。因此表达式(0|1)*11(1|01)*表示所有由0和1组成的，以两个1后面加上其中的0都要立即加上一个1的任意序列结尾的字符串。而最后的因子(ε|0)表示“可选的0”，也就是说，刚刚描述的字符串后面可能还有一个0，也可能没有，要看我们的选择。
10.5.6　习题
1. 在示例10.13中，我们描述了正则表达式(a|ab)(c|cb)，并看到它的语言是由ac、abc和abbc这3个字符串组成的，也就是说，一个a和一个c，中间被0到2个b分隔开。再写两个定义该语言的正则表达式。
2. 写出定义下列语言的正则表达式。
(a) 对应6个C语言比较运算符=、&=、&、&=、&和!=的字符串。
(b) 所有由0和1组成且结尾为0的字符串。
(c) 所有由0和1组成且至少有一个1的字符串。
(d) 所有由0和1组成且至多有一个1的字符串。
(e) 所有由0和1组成且至右起第三位是1的字符串。
(f) 所有由小写字母按已排序次序组成的字符串。
3. * 写出定义下列语言的正则表达式。
(a) 所有由a和b组成，满足其中由a组成的子序列长度都是偶数的字符串。也就是说，诸如bbbaabaaaa、aaaabb和ε这样的字符串，而abbabaa和aaa就不是。
(b) 由C语言中float类型的数字表示的字符串。
(c) 由0和1组成且具有偶校验（即含偶数个1）的字符串。提示：将偶校验字符串视作具有偶校验的基本字符串（要么是一个0，要么是只由0分隔的一对1）的串接。
4. ** 写出定义下列语言的正则表达式。
(a) 不是关键字的C语言标识符组成的集合。如果忘记了某些关键字也是没关系的，本题的重点在于表示那些不在某个相当大的字符串集合中的字符串。
(b) 所有由a、b和c组成，而且满足任何两个连续位置上的字母都不相同的字符串。
(c) 由两个不同的小写字母形成的所有字符串构成的集合。提示：大家可以用“蛮力”来解决问题，不过用两个不同的字母构成的字母对有650个。更好的思路是进行一些分组。例如，相对较短的表达式(a|b|…|m)(n|o|…|z)就能覆盖这650个字母对中的169个。
(d) 所有由二进制数字0和1组成的，表示为3的倍数的整数的字符串。
5. 根据取并、串接和闭包运算符的优先级，为以下正则表达式加上括号，以表示操作数的恰当分组。
(a) a|bc|de
(b) a|b*|(a|b)*a
6. 从下列正则表达式中删除多余的括号，也就是说，删除那些分组可以由运算符的优先级以及取并
和串接的结合性（因此为邻接的取并或邻接的串接分组是无关紧要的）暗示出的括号。
(a) (ab)(cd)
(b) (a|(b(c)*))
(c) (((a)|b(c|d))
7. * 描述由以下正则表达式定义的语言。
(c) (a|b)*
(d) (a*b*)*
(e) (a*ba*b)*a*
(g) R **，其中R 是任意正则表达式。
10.6　UNIX 对正则表达式的扩展
UNIX操作系统中有不少命令利用了类似正则表达式的表示法来描述模式。即便对UNIX操作系统与其中的大部分命令并不熟悉，了解这些表示法也还是很实用的。我们发现正则表达式至少用在如下3类命令中。
1. 编辑器。UNIX编辑器ed和vi，以及大多数现代文本编辑器，让用户可以在找到某给定模式实例的位置扫描文本。这一模式是由正则表达式指定的，虽然没有一般的取并运算符，只有下面将要讨论的“字符类”。
2. 模式匹配程序grep及类似程序。UNIX命令grep会对文件进行扫描，检查文件的每一行。如果该行包含某个能与由正则表达式指定的模式匹配的子串，就将该行打印出来（grep代表globally search for regular expression and print，即全局查找正则表达式并打印）。grep命令本身只接受正则表达式的子集，而扩展的命令egrep则可以接受完整的正则表达式表示，而且包含了一些其他的扩展。命令awk允许我们进行全面的正则表达式搜索，并且把文本行当作关系的元组来处理，从而使我们可以对文件执行选择和投影这样的关系代数运算。
3. 词法分析。UNIX命令lex对编写编译器代码及类似任务而言是很使用的。编译器第一件必须完成的事就是将程序分割为一个个标记（token），它们是逻辑上结合在一起的子字符串。标记的例子包括标识符、常量、then这样的关键字，以及+或&=这样的运算符。每种标记类型都可以由一个正则表达式来指定，比方说，示例10.17就展示了如何指定“标识符”标记类。lex命令让用户可以用正则表达式指定标记类。这样就形成了可以用作词法分析器的程序，也就是可以把输入分解为标记的程序。
10.6.1　字符类
我们经常需要写出表示字符集合，或者严格地讲，是表示长度为1的字符串（每个字符串都是由集合中不同的字符构成）组成的集合的正则表达式。因此，在示例10.17中，我们定义了表达式letter 表示任何由一个大写字母或小写字母组成的字符串，并定义了表达式digit 表示任何由一个数字构成的字符串。这些表达式都是相当长的，而UNIX提供了一些重要的简写。
首先，可以用方括号把任意字符表括起来，用来代表对这些字母取并的正则表达式。这样的表达式就叫作字符类。例如，表达式[aghinostw]表示出现在单词washington中的字母组成的集合，而[aghinostw]*则表示只由这些字母形成的字符串所构成的集合。
其次，我们并非总是需要明确地列出所有的字符。回想一下，字母几乎一直都是用ASCII编码的。这种编码会为各种字符指定相应的位串（很自然地就可以解释为整数），而且它是以一种合理的方式来完成这一工作的。例如，ASCII编码为大写字母分配了连续的整数。同样，它也为小写字母以及数字分配了连续的整数。
如果在两个字符间加上破折号，就不仅表示这些字符，而且表示了编码在这两个字符编码之间的所有字符。
示例 10.19
我们可以通过[A-Za-z]定义大写字母与小写字母。前3个字符A-Z表示编码处于A和Z之间的所有字符，也就是所有的大写字母。而接下来的3个字符a-z则表示所有的小写字母。
顺便提一句，因为破折号有这样一种特殊含义，所以如果想要定义包含-的字符类，就一定要谨慎行事。必须把破折号放在这列字符的第一个位置或最后一个位置。例如，可以通过[-+*/]来指定4四种算术运算符组成的集合，但如果写成[+-*/]的形式就是错误的，因为+-*这样的范围会表示编码在+和*的编码之间的所有字符。
10.6.2　行的开头和结尾
因为UNIX命令经常要处理单行文本，所以UNIX正则表达式表示法中包含了用于表示行的开头和结尾的特殊符号。符号^表示行的开头，而$表示行的结尾。
示例 10.20
10.3节图10-12中的自动机是从一行的开头处启动的，它接受的文本行刚好是那些只由单词washington中的字母组成的文本行。可以将这种模式表示为UNIX正则表达式：^[aghinostw]*$。口头上讲，该模式就是“行的开头，后面跟上由单词washington中的字母组成的任意序列，再加上行的结尾”。
举个这种正则表达式使用方式的例子，UNIX命令行：
grep'^[aghinostw]*$ /usr/dict/words
将打印出词典中所有只由来自washington的字符组成的单词。在这种情况下，UNIX要求该正则表达式被写为引用的字符串。这一命令的效果就是指定的文件/usr/dict/words中每一行都会被检查。如果它含有任何处在由该正则表达式表示的字符串集合中的子字符串，那么这一行就要被打印出来，否则这一行就不会被打印。请注意，这一行的开头符号与结尾符号已然存在了。假设它们不存在。因为空字符串是在由正则表达式[aghinostw]*表示的语言中的，所以我们会发现每一行都有一个子字符串（即ε）位于该正则表达式的语言中，因此每一行都会被打印出来。
为字符赋予字面意义
顺便说一下，因为字符^和$在正则表达式中被赋予了特殊意义，所以看起来没办法在UNIX正则表达式中指定这些字符本身了。不过，UNIX用到了反斜杠\，作为转义字符。如果我们在字符^或$之前加上反斜杠，那么这两个字符形成的组合就会被解释为第二个字符的字面意义，而不是其特殊含义。例如\$表示UNIX正则表达式中的$字符。同样，两道反斜杠就被解释为一个反斜杠，而不含有其转义字符的特殊意义。而UNIX正则表达式中的字符串\\$表示的是反斜杠字符后面跟上行的结尾。
还有不少其他的字符也被UNIX在某些情形下赋予了特殊意义，而这些字符也总是能表示它们的字面意义，也就是，通过在它们之前使用反斜杠来“除掉”它们的特殊意义。例如，只有这样处理方括号，方括号在UNIX正则表达式中才不会被解释为字符类分隔符。
10.6.3　通配符
符号.在UNIX正则表达式中代表“除换行符之外的任意字符”。
示例 10.21
正则表达式
.*a*e.*o.*u.
表示按次序包含5个元音字母的所有字符串。我们可以利用grep与该正则表达式来扫描词典，查找单词中5个元音字母按递增次序出现的所有单词。不过，如果忽略掉开头和结尾位置的.*，处理将更具效率，因为grep是按子字符串搜索指定的模式，而不是整行搜索，除非我们显式地包含了表示行开头和行结尾的符号。因此命令
grep'a.*e.*i.*u' /use/dict/words
将会找到含有子序列aeiou的所有单词并将其打印出来。
这些点号会匹配除字母之外的字符，这一实情并不重要，因为在/usr/dict/words文件中除了字符和换行符之外没有其他字符。不过，如果点号可以匹配换行符，那么这一正则表达式就会允许grep一次使用多行来找出依次出现的5个元音字母。不过像本例这样的例子都是点号被定义为不匹配换行符的例子。
10.6.4　额外的运算符
UNIX命令awk和egrep中的正则表达式还含有一些额外的运算符，具体如下。
1. 与grep不同的是，awk和egrep命令还允许取并运算符|出现在它们的正则表达式中。
2. 一元后缀运算符?和+没有允许我们定义额外的语言，但它们通常会让表示语言的工作变得更简单。如果R 是正则表达式，则R?代表ε |R，也就是可选的R。所以L(R?)是L(R )∪{ε }。R+代表RR *，或者等价地讲就是“R 中的单词出现一次或多次”。因此，L(R+)＝L(R )∪L(RR )∪L(RRR )…。特别要说的是，如果ε 在L(R )中，那么L(R+)和L(R *)表示相同的语言。而如果ε 不在L(R )中，那么L(R+)就表示L(R *)-{ε }。运算符 ? 和+与 * 有着相同的结合性与优先级。
示例 10.22
假设我们想通过正则表达式来指定由非空数字串与一个小数点组成的实数。将该表达式写为[0-9]*.[0-9]*是不正确的，因为这样一来，只由一个点号组成的字符串也会被视作实数。该表达式利用egrep的一种写法是
[0-9]+ \.[0-9]*\.[0-9]+
在这里，取并的第一项涵盖了那些小数点左侧至少有一个数字的实数，而第二项则涵盖了以小数点开头，因此在小数点后必须至少有一位数字的那些实数。请注意，放在点号之前的反斜杠是为了表明这里的点号不具有约定的“通配符”含义。
示例 10.23
利用如下egrep命令可以扫描输入中那些字母严格按照字母表增序排列的行。
egrep '^a?b?c?d?e?f?g?h?i?j?k?l?m?n?o?p?q?r?s?t?u?v?w?x?y?z?$'
也就是说，我们会扫描每一行，看看在行的开头和结尾之间是否有可选的a、可选的b，等等。例如，含有单词adept的一行就能匹该表达式，因为a、d、e、p和t之后的?可以解释为“出现一次”，而其他的?可以解释为“没有出现”，也就是ε。
10.6.5　习题
1. 为以下字符类写出表达式。
(a) 所有属于C语言运算符和标点符的字符，例如+和圆括号。
(b) 所有小写元音字母。
(c) 所有小写辅音字母。
2. * 如果可以使用UNIX，编写egrep程序检查/usr/dict/words文件，并找到下列单词：
(a) 所有以dous结尾的单词；
(b) 所有只含一个元音字母的单词；
(c) 所有原音字母与辅音字母交替出现的单词；
(d) 所有含四个或更多个连续辅音字母的单词。
10.7　正则表达式的代数法则
两个正则表达式是可以表示同一语言的，就像两个算术表达式可以表示其操作数的相同函数那样。举例来说，x+y 和y+x 这两个表达式就表示x 和y 的相同函数。同样，不管用什么正则表达式来替换R 和S，正则表达式R |S和S |R都表示同一语言，证据就是取并运算也是具有交换性的。
简化正则表达式往往是很实用的。我们很快就会看到，在根据自动机构造正则表达式时，经常会构造出过于复杂的正则表达式。代数等价可以让我们“简化”表达式，也就是说，把一个正则表达式替换为另一个操作数和（或）运算符更少却又表示相同语言的正则表达式。这一过程类似于在处理算术表达式时对繁冗的表达式进行的那些简化。例如，可以将两个很大的多项式相乘，然后通过分组相似项来简化结果。再比如，我们在8.9节中简化了关系代数表达式从而获得更快的求值速度。
如果L(R )=L(S )，就说两个正则表达式R 和S 是等价的，记作R ≡S。如果这样的话，可以说R ≡S是一种等价。在接下来的内容中，我们将假设R、S 和T 是任意的正则表达式，并以这些操作数来陈述要讨论的等价关系。
等价的证明
在本节中，我们要证明若干涉及正则表达式的等价关系。回想一下，两个正则表达式的等价是说，不管为其变量替换怎样的语言，这两个表达式的语言都是相等的。因此我们可以通过证明两种语言，也就是两个字符串集合的相等性，来证明正则表达式的等价。一般而言，要通过证明两个方向上的包含关系来证明集合S1和集合S2是等价的。也就是说，证明S1?S2，还要证明S2?S1。两个方向对证明集合相等都是必要的。
10.7.1　取并和串接与加法和乘法的类比
在本节中，我们要列举与正则表达式的取并、串接和闭包运算符有关的最重要的那些等价关系。首先要从取并和串接运算与加法和乘法运算的类比开始。正如我们将要看到，这种类比并不是很精确，主要因为串接是不具备交换性的，而乘法当然是具备交换性的。不过，这两对运算之间还是存在诸多相似性。
首先，取并和串接都具有单位元。取并运算的单位元是?，而串接运算的单位元是ε。
(1) 取并的单位元。(?|R )≡(R |?)≡R。
(2) 串接的单