1 / 20
实验三（一）NFADFA（2小时）
一. 问题描述
NFADFA。
1. 实验目的：学会编程实现子集构造法。
2. 实验任务：存储NFA与DFA，编程实现子集构造法将NFA转换成DFA。
3. 实验内容：（1）确定NFA与DFA的存储格式，为3个以上测试NFA准备好存储文件。（2）用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。（3）经测试无误。测试不易。可求出NFA与DFA的语言集合的某个子集（如长度小于某个N），再证实两个语言集合完全相同！（4）测试用例参考：将下列语言用RE表示，再转换成NFA使用：
(a) 以a开头和结尾的小字字母串；a (a|b|…|z)*a | a
(b) 不包含三个连续的b的，由字母a与b组成的字符串；( | b | bb) (a | ab | abb)*
(c) (aa|b)*(a|bb)*
二．算法描述
1. NFA的输入：
分别输入NFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”等内容，并保存在设定的变量中。
2. NFA的存储与读写：
将上述NFA的五元组保存在一个文本文件中。存储格式如下所示（以下图中NFA为例）：
2 // 字符集中的字符个数 (以下两行也可合并成一行)
a b // 以空格分隔的字符集。 2 / 20 4 // 状态个数 (以下两行也可合并成一行)
1 2 3 4 // 状态编号。若约定总是用从1开始的连续数字表示，则此行可省略
1 // 开始状态的编号。若约定为1，则此行可省略
1 // 结束状态个数。若约定为1，则此行可省略
3 // 结束状态的编号
3 2 1 // 状态1的所有出去的转换。按字符集中的字符顺序给出，并在最左边加上一列关于的转换。-1表示出错状态。多个状态用逗号分隔。
-1 1 -1
-1 3 4
-1 -1 3
3. 基本算法描述
存储格式如上所示，程序开始时，从文件中读取数据以获得NFA中的各种信息。根据子集构造法，构造相应的函数。
构造正规式相应的DFA
构造正规式相应的DFA：1(0|1)*101
按照以下三步：
（1）由正规表达式构造转换系统（NFA）
（2）由转换系统（NFA）构造确定的有穷⾃动机DFA
（3）DFA的最⼩化
答：（1）⾸先构造与正规式1（0|1）*101相应的NFA，然后再将NFA确定化。为正规式构造NFA的⽅法为“语法制导”法，即依据正规式的语法构造来构造。⾸先将正规式r=1（0|1）*101分解成r=r1,r2r3，其中：r1=1，r2=（0|1）*，r3=101。
对于r1，有：
对于r2，有：0,1
对于r3，有：
因此，与正规式r=r1r2r3相对应的NFA如图所⽰为：0,1展开为：
1
（2）将NFA转换成DFA
采⽤⼦集法，即DFA的每个状态对应NFA的⼀个状态集合。构造DFA的状态集C，假定
DFA的状态转换图
1
（3）化简DFA：分割法，把DFA的状态集分成⼀些不想交的⼦集，使得不同的两⼦集的状态是可区别的，同⼀⼦集的状态是等价的。⾸先，将状态分成两个⼦集：⼀个由终态组成，⼀个由⾮态组成：{T0，T1，T2，T3，T4} {T5}{T0，T1，T2，T3} {T4} {T5}
{ T0，T1，T2} {T3} {T4} {T5}
{T0} {T1，T2} {T3} {T4} {T5}
在等价状态⼦集{T1，T2}中选状态T2做代表，消去其他状态T1，把从消去状态T1射出和
射⼊的弧都引到代表状态T2上，得到化简后的DFA：
1 / 9 试题（共10道）
1.设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
2.已知文法G[S’] :S’ →S
S→rD
D→D,i
D→i
(1)构造G[S’]的识别活前缀的有穷自动机DFA。
(2)该文法是LR(0)文法吗？为什么？
3.已知文法G[S’] :S’ →S (1)
S→AAA (2)
A→1A (3)
A→0 (4)
(1)构造G[S’]的识别活前缀的有穷自动机DFA。
(2)构造相应的LR(0)分析表。
4.构造一个DFA，它接受={a，b}上所有包含ab的字符串。
5. 构造正规式 (0|1)*00 相应的DFA并进行化简。
6. 构造以下正规式相应的NFA，再确定化
10（1|0）*11
7. 设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。
(1)试写出描述 L 的正规表达式；
(2)构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的
NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。
8.已知 NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的
DFA。
9. 给出下述文法所对应的正规式：
1 / 7 第二章 词法分析
2.1 完成下列选择题：
(1) 词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置
c. 单词的种别编码和自身值 d. 单词自身值
(2) 正规式M1和M2等价是指 。
a. M1和M2的状态数相等
b. M1和M2的有向边条数相等
c. M1和M2所识别的语言集相等
d. M1和M2状态数和有向边条数相等
(3) DFA M(见图2-1)接受的字集为 。
a. 以0开头的二进制数组成的集合
b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合
d. 含偶数个0的二进制数组成的集合
【解答】
(1) c (2) c (3) d
图2-1 习题2.1的DFA M
2.2 什么是扫描器？扫描器的功能是什么？
【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f定义如下：
f(x,a)={x,y} f{x,b}={y}
f(y,a)=Φ f{y,b}={x,y}
试构造相应的确定有限自动机M′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。
