【编译原理】第二章部分课后题答案

《编译原理（第三版）》陈意云著

T 2.3

叙述由下列正规式描述的语言

1. 

   正规式规定开头和结尾必须包括0，中间由0或1的闭包构成，可以看出该正规式描述的语言包含的串长度至少为2，所以总结为：以0开头和结尾的长度至少是2的串01.

2. 

   内层括号中是对空和0的选择，再与外面的1的闭包相连接，可能构成的串有：、、 、、、，再加上外层的闭包，可以让 的个数变成任意多且可以为空串的闭包，所以总结为：所有的01串（包含空串）.

3. 

   描述了长度为3，第一位为0的01串，在前面加上0或1的闭包使得串可以以任意二进制或空开头，所以结论为：至少包括三位且倒数第三位是0的01串.

4. 

   三个1是必然存在于串中的，而剩下0的闭包则说明0的个数为任意多，所以结论为：含有三个1的01串.

5. 

   第一个闭包可以选择00或11，后面的两个内层闭包所描述的语言与第一个闭包相同，外层闭包让其内部的串可以出现任意次。由于该正规式过于复杂，所以可以将其描述的语言简单概括为：含有偶数（含0个）个0和偶数（含0个）个1的01串.

T 2.4

为下列语言写出正规定义

1. 包含5个元音的所有字母串，其中每个元音只出现一次且按顺序排列。

   不含五个元音的任意字符：，记为

   故，

2. 按词典序排列的所有字母串。

   

3. 某语言的注释，它是以开始并以结束的任意字符串，但它的任何前缀（本身除外）不以结尾。

   不含，的任意字符记为

   不含的任意字符串可以表示为

   故，

4. 相邻数字都不相同的所有数字串。

5. 最多只有一处相邻数字相同的所有数字串。

6. 由偶数个0和偶数个1组成的所有01串。

   

7. 由偶数个0和奇数个1组成的所有01串。

   

8. 不含字串011的01串。

   

9. 字母表上，不会相邻出现的所有串。

   

T 2.7

用算法 2.4 为下列正规式构造不确定有限自动机，给出它们处理输入串 的状态转化序列

方式一：（算法 2.4）

方式二：（分裂法）

方式三：

T 2.8

用算法2.2把习题2.7中的第三问的NFA变换成DFA。给出它们处理输入串 的状态转换序列

为了书写的方便，将上面 NFA 中的状态重新编号，得到下图：

上图的 NFA 等价的 DFA 的开始状态是 ，记为 ；

输入字母表是 ，计算 ，由于只有状态 能发生 转换，所以 ，故 ，称该集合为 ；

计算 ，由于只有状态 能发生 转换，所以 ，故 ，称该集合为 ；

对新集合 和 重复上面的过程可以得到完整的转换表如下：

根据转换表得到等价的 DFA 如下：

T 2.11

可以从正规式的最简 DFA 同构来证明两个正规式等价。使用这种计数，证明正规式 、 和 等价

与 T 2.8 类似，先将上面的 NFA 中的状态重新编号便于计算。

对应的 NFA：

对应的状态转换表：

对应的 DFA：

对应的最简 DFA：

初始划分两个子集：接受状态子集 和非接受状态 ；

不可进一步划分，所以对 进一步划分；

这说明 是不可区分的子集，故无需进一步划分。

最终上图即为最简 DFA。

对应的 NFA：

对应的状态转换表：

对应的 DFA：

对应的最简 DFA：

由于 对应的 DFA 与 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即上图。

的 DFA 在 T 2.8 中已经得到，由于其与 对应的 DFA 完全一致，所以最终化简得到的 DFA 也是一样的，即：

由于已知“最简 DFA 同构的正规式等价”可知，三者的最简 DFA 同构，所以三个正规式等价。

T 2.12

为下列正规式构造最简的 DFA

对应的 NFA 如下：

对应的转换表如下：

对应的 DFA 如下：

对应的最简 DFA 如下：

初始划分两个子集：接受状态子集 和非接受状态子集 ；

对于接受状态子集，输入字符 ，状态 和状态 分别变换到状态 和状态 ，二者不在同一子集中，所以需要划分成 、；

对于非接受状态子集，输入字符 ，状态 和状态 均变换到状态 ，而状态 变换到状态 ，属于另一个子集，所以初步划分为 、；输入字符 ，状态 和状态 均变换到状态 ，所以两个状态不可区分，无需进一步划分。

故，最终状态子集为 、、 和 。

为了绘制 DFA 方便，令 为状态 ， 为状态 ， 为状态 ， 为状态 。

方法一： 子集构造法得到的 NFA 如下：

对应的转换表如下：

方法二： 分裂法得到的 NFA 如下：

对应的转换表如下：

可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的DFA也一致。

对应的 DFA 如下：

对应的最简 DFA 如下：

初始划分两个子集：接受状态子集 和非接受状态子集 ；

对于接受状态子集，分别输入字符 和字符 ，可将原集合划分为 和 ；

对于非接受状态子集，分别输入字符 和字符 ，可将原集合划分为 和 ；

对 集合进一步划分成 和 ；

对 集合进一步划分成 和 ；

对 集合进一步划分成 和 ；

对 集合进一步划分成 和 ；

故，最终状态子集为 、 、 、 、、 、 和 。

为了绘制 DFA 方便，令 为状态 ， 为状态 ， 为状态 ， 为状态 ， 为状态 、 为状态 、 为状态 、 为状态 。

方法一： 子集构造法得到的 NFA 如下：

对应的转换表如下：

可以看出“子集构造法”和“分裂法”得到的状态转换表一样，所以化出的DFA也一致。

方法二： 分裂法得到的 NFA 如下：

对应的转换表如下：

对应的 DFA 如下：

对应的最简 DFA 如下：

初次划分： 和

第二次划分：、、 和

第三次划分：、、、、、、 和

第四次划分：、、、、、、、、、、、、、、 和

最终划分结果为：、、、、、、、、、、、、、、 和

为了绘制 DFA 方便，令 为状态 ， 为状态 ， 为状态 ， 为状态 ， 为状态 、 为状态 、 为状态 、 为状态 ， 为状态 ， 为状态 ， 为状态 ， 为状态 ， 为状态 、 为状态 、 为状态 、 为状态 。

T 2.13

构造一个 DFA，它接受 上 和 的个数都是偶数的字符串

对于一个01串，无论其 0 和 1 的个数有多少，总属于下面四种情况之一：

0：0和1的个数都是偶数；

1：0的个数是偶数，1的个数是奇数；

2：0的个数是奇数，1的个数是偶数；

3：0和1的个数都是奇数.

无论上述哪种情况，在01串后添加一个0或1后，总会处于另一种情况中，因此构造的 DFA 可以通过四个状态表示出来：

T 2.14

构造一个 DFA，它接受 上能被 整除的二进制数

一个数对5取模，存在五种结果，结果为0、1、2、3、4。结果为0对应的是接受状态，其余是非接受状态。这样便可通过五个状态构造 DFA。

0：对5取模得0；

1：对5取模得1；

2：对5取模得2；

3：对5取模得3；

4：对5取模得4.

T 2.15

构造一个最简的 DFA，它接受所有大于 的二进制整数

根据题意，先简单地将状态分为六种，为、、、、、和大于的整数。

0：对应二进制整数为0；

1：对应二进制整数为1；

2：对应二进制整数为2；

3：对应二进制整数为3；

4：对应二进制整数为4；

5：对应二进制整数为5；

6：对应二进制整数大于5.

初步构造 DFA：

对上面的 DFA 进行化简：

初步划分为接受状态子集 和非接受状态子集 ；

接受状态子集无法进一步划分；

对非接受状态子集进一步划分：

，其中状态 转换到状态 ，状态 转换到状态 ，状态 转换到状态 ，状态 均转换到状态 。

，其中状态 转换到状态 ，状态 转换到状态 ，状态 转换到状态 ，状态 均转换到状态 。

由于 属于同一个子集，所以 仍属于同一子集，而由于 转换到了另一个不同的子集中，所以 被归为新的一个子集，子集 和子集 代替了原先的子集 ；

现在全部子集为 、 和 ，分别对子集 和子集 进一步划分：

，其中状态 转换到状态 ，状态 转换到状态 ，状态 转换到状态 。

，其中状态 转换到状态 ，状态 转换到状态 ，状态 转换到状态 。

在输入字符为的情况下，状态 和 状态 均转换到同一集合 中，但是状态 转换到了另一个集合 中，所以状态 将被划分到与状态 和状态 不同的子集中；在输入字符为的情况下，状态 转换到子集 中，而状态 转移到子集 中，根据子集划分的要求“两个状态 和 被划分到同一子集中，当且仅当对任意输入符号 ，状态 和 转换到本次划分前的同一子集中”，所以状态 和 状态 也要被划分到不同子集。故，经过本次划分，得到全部子集 、、、 和 。

，所以无需进一步划分。

最终得到全部子集 、、、 和 。令 ，，，，，最简 DFA 如下：