资源描述：
《北航计算机学院编译习题讲解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章:词法分析3.1词法分析的功能3.2词法分析程序的设计与实现–状态图3.3词法分析程序的自动生成–有穷自动机、LEX2008年7月2日1补充正则文法15264NFA正则表达式3DFA最小化2008年7月2日2P67:1．画出下述文法的状态图〈Z〉::=〈B〉e〈B〉::=〈A〉f〈A〉::=e
2、〈A〉e使用该状态图检查下列句子是否是该文法的合法句子f，eeff，eefe解：eefeSABZf，eeff不是该文法的合法句子，eefe是该文法的合法句子2008年7月2日30P67:2.有下列状态图，其中S为初态，Z为终态。A0开始（1）写出相应的正
3、则文法：S1（2）写出该文法的V，Vn和Vt；0Z（3）该文法确定的语言是什么？¾出错点：第(3)小题，文法确定的语言,很多同学回答出了，但是写的格式很不规范。解：（1）Z→A1
4、0A→A0
5、0（2）V={A,Z,0,1}Vn={A,Z}Vt={0,1}（3）L(G[S])={0或0n1,n≥1}0
6、00*12008年7月2日4P67:5．令A，B，C是任意正则表达式，证明以下关系成立：A
7、A=A（A*）*=A*A*=ε
8、AA*（AB）*A=A（BA）*（A
9、B）*=（A*B*）*=（A*
10、B*）¾该题做得不错！但少部分同学最后一个等式没有证明。另外
11、，有些同学虽然证对了，但是过程比较烦琐或者是不规范。2008年7月2日5•证明：正则表达式表示的语言相等，则正则表达式相等⑴若用L表示正则表达式A表示的语言，则A∣A表示的语言是：L∪LAAA因为L∪L＝L所以A∣A＝AAAA⑵（A*）*表示的语言为(L*)*AA*表示的语言为L*A(L*)*=(L*)0∪(L*)1∪(L*)2…AAAA={ε}∪(L*)1∪(L*)2…AA下面用数学归纳法证明(L*)n＝L*，n≥1AAn＝1时，显然成立假定n＝k时，(L*)k＝L*，则n＝k＋1时AA(L*)k＋1＝(L*)kL*＝L*L*＝（L0∪L1∪L2…
12、）L*AAAAAAAAA＝L0L*∪L1L*∪L2L*…AAAAAA＝（L0∪L1∪L2…)∪L1（L0∪L1∪L2…)∪L2（L0∪L1∪AAAAAAAAAAL2…)…A＝（L0∪L1∪L2…)∪(L1∪L2∪L3…)∪(L2∪L3∪L4…)…AAAAAAAAA＝L0∪L1∪L2…AAA＝L*A∴(L*)k＋1＝L*，故(L*)n＝L*，n≥1AAAA∴(L*)*={ε}∪(L*)1∪(L*)2…={ε}∪L*＝L*AAAAA2008年7月2日6⑶ε︱AA*所表示的语言是:{ε}∪L·L*AA＝L0∪L（L0∪L1∪L2∪…）AAAAA＝L0∪L1
13、∪L2∪…＝L*AAAA故ε︱AA*＝A*⑷(LL)*L=({ε}∪LL∪LLLL∪LLLLLL∪…)LABAABABABABABABA=L∪LLL∪LLLLL∪LLLLLL∪L…AABAABABAABABABA=L∪({ε}∪LL∪LLLL∪…)ABABABA=L(LL)*ABA∴(AB)*A=A(AB)*2008年7月2日7⑸三个表达式所描述的语言都是L和L中符号串的任意组合AB∴（A
14、B）*=(A*B*)*=(A*
15、B*)*2008年7月2日8P67:6.构造下列正则表达式相应的DFA（1）1（0
16、1）*
17、0（2）1（1010*
18、1（010）*
19、1）*0¾在状态图中终止状态没有用双线圆标出2008年7月2日9（1）与1（0
20、1）*
21、0对应的NFA为：0,12008年7月2日10确定化：0q11startq010q22008年7月2日11（2）1（1010*
22、1（010）*1）*0ε0101εCDEFεStart10εABMNε10101εGHIJKLεε2008年7月2日121（1010*
23、1（010）*1）*0E010DF1εStart10ABC11G00HI12008年7月2日132008年7月2日14P68：8.把图3.24的（a）和（b）分别确定化aa,b开始ab01a{0}{0,1
24、}{1}{0,1}{0,1}{1}{1}{0}--a开始a00,1abb12008年7月2日15P68:10构造一DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。(0
25、10)*01开始AB02008年7月2日16补充题1.有正则表达式1(0
26、1)*101,构造DFA,并最小化ε1εDEεStart1εε101ABCHIJKLε0εFGε01{A}--{BCDFI}{BCDFI}{GHICDF}{EHICDFJ}{GHICDF}{GHICDF}{EHICDFJ}{EHICDFJ}{GHICDFK}{EHICDFJ}{G
27、HICDFK}{GHICDF}{EHICDFJL}{EHICDFJL}{GHICDFK}{EHICDFJ}2
