第4章 词法分析
重点内容：正规式转化为DFA a、 正规式->NFA
b、 NFA -> DFA（子集法） c、 DFA化简（分割法） 题目1：课件例题：
a、 为 R=(a|b)*(aa|bb)(a|b)*构造 NFA
b、 从NFA构造DFA的算法
c、 化简
1
题目2：
4.7 例1：构造正规式相应的DFA：1(0|1)*101 按照以下三步：
（1）由正规表达式构造转换系统（NFA）
（2）由转换系统（NFA）构造确定的有穷自动机DFA （3）DFA的最小化 答：（1）构造与1(0|1)*101等价的 NFA
X 1(0|1)*101 Y 1 (0|1)* 1 0 1 X A B C D Y 0,1 1 1 0 1 X A B C Y
（2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合： 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB
除X，A外，重新命名其他状态：
0 1 X A A A B
2
B C D C A C B D B 1、将M的状态分成非终态和终态集{X,A,B,C}和{D}。
2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。 最后生成DFA：
0 0 1 X A 1 1 B 0 C 1
1 D 0
题目3：自习、书本练习4.7，参考答案见《z4 书本练习4.7.doc》 已知文法G[S]：
S→aA|bQ A→aA|bB|b B→bD|aQ Q→aQ|bD|b E→aB|bF F→bD|aE|b 1、 构由于不可到达，去除E、F相关的多余产生式 2、 由新的G[S]构造NFA如下
3、 NFA的转换表： S A B,Z Q D D,Z B a A A Q Q A A Q b Q B,Z D D,Z B D D 0 1 2 3 4 5 6 **01 1 3 3 1 1 3 3 2 4 5 6 4 4
4、子集法重命名状态：（上标0：初态，*：终态）
a b 3