第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