编译原理复习题目集答案解析 下载本文

第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