《第二、三章习题讲分解.ppt》由会员分享,可在线阅读,更多相关《第二、三章习题讲分解.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第二、三章习题讲解第二、三章习题讲解2008-10-282.1 考虑下面的上下文无关文法:S SS+|SS*|aa)试说明如何使用该文法生成串aa+a*。b)试为aa+a*构造一个分析树。c)该文法产生的语言是什么?ANSWER:a)S SS*SS+S*aa+a*b)图c)以a为变量,+和*为二元操作符的后缀表达式22.2 下面的文法产生什么语言?a)S0S1|010n1n(n=1,2,)b)S+SS|-SS|a以a为变量,+和-为二元操作符的前缀表达式c)SS(S)S|括号的匹配d)SaSbS|bSaS|由相同数目的a、b组成的字符串,或者空串。3e)Sa|S+S|SS|S*|(S)以a为数
2、据元素,具有合并、连接、闭包和括号操作符的表达式。a是表达式,若S是表达式则S+S(表达式的合并)、SS(表达式的串联)、S*(表达式的闭包运算)都是表达式。4注意事项不是终结符,应该省略。但是如果包含空串,则需特别强调。产生式可以交替使用描述生成何种语言时,应当描述完整的字母表52.3 练习2.2中哪些文法具有二义性?c、d、e具有二义性。可通过画某个串的分析树来说明67 S aSbS|bSaS|a)试说明此文法是二义性的.可以从句子abab有两个不同的最左推导来说明.S aSbS abS abaSbS ababS abab lm lm lm lm lm S aSbS abSaSbS aba
3、SbS ababS abab lm lm lm lm lm 句子abab有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.8(b)对于句子abab构造两个相应的最右推导.S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm(c)对于句子abab构造两个相应的分析树.判断一个文法是否具有二义性,可以通过判断是否存在一个具有多棵分析树的记号串。3.3 识别下面的各段程序中构成记号的词素,并给出每个记号的合理属性值:程序:int max(i,j)int i,j
4、;/*返回整数i和j的最大者*/return ij?i:j;9词素记号属性intintmaxid指向符号表max条目的指针(标点符号左括号iid指向符号表i条目的指针,标点符号逗号jid指向符号表j条目的指针)标点符号右括号;标点符号分号returnreturn操作符大于号?操作符问号:操作符冒号标点符号右大括号标点符号左大括号10注意事项1.记号token(终结符),模式pattern,词素lexeme(源程序的字符序列)2.可构成token(记号)的:关键字,操作符,标识符,常量,字符串,标点符号3.每个词素都要一一记录4.注释是在词法分析时忽略的,而词法分析器对程序采取非常局部的观点。5
5、.不是每个token都要有属性1112(a)0(0|1)*0(b)(|0)1*)*由0和1组成且以0开始和结束的符号串全体.(c)(0|1)*0(0|1)(0|1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.3.6 试描述下列正规表达式所表示的语言:13(d)0*10*10*10*(e)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*有且只有3个1的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.(aa|bb)
6、|(ab|ba)(aa|bb)*(ab|ba)*注意事项在描述语言的时候应该准确,精简。语言给定字母表上任意一个字符串集合。句子(字)属于语言的字符串,字母表中符号的有穷序列。空字符串和空集143.7 试写出下列语言的正规定义:a)包含5个元音的所有字母串,其中元音按顺序出现。X=辅音字母全体(X|(A|a)*(A|a)(X|(E|e)*(E|e)(X|(I|i)*(I|i)(X|(O|o)*(O|o)(X|(U|u)*(U|u)X*15保证元音字母至少出现一次b)按词典递增序排列的所有字母串。(a|A)*(b|B)*(c|C)*.(z|Z)*1617 d)没有重复出现的数字的数字符号串全体.
7、e)最多有一个重复出现的数字的数字符号串全体令 ri=i|,i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1.i9P(0,1,2.,9)i ri0ri1.ri9i(0,1,2.,9)i0i1.i9P(0,1,2.,9)18 f)带有偶数个0和奇数个1的由0和1组成的符号串全体.E为带有偶数个0和1的由0和1组成的符号串全体.即(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*E 1 E|E 0 E 1 E 0 E h)不包含子串011的由0和1组成
8、的符号串全体.i)不包含子序列011的由0和1组成的符号串全体1*0*(10*|)1*(0|(01)*19 h)不包含子串011的由0和1组成的符号串全体.i)不包含子序列011的由0和1组成的符号串全体1*(0|(01)*1*0*(10*|)(00|11)(01|10)(00|11)(01|10)(00|11)所有由偶数个0和偶数个1构成的串。另外,和该正规式等价的正规式有(00|11|(01|10)(00|11)(01|10)。更简单的描述(00|11|(01|10)(00|11)(01|10)它是基于这样的考虑,满足要求的最简单的串有三种形式(空串除外):1002113(01|10)(0
9、0|11)(01|10)它们任意多次的重复构成的串仍然满足要求。20写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。even_0_even_1(00|11)(01|10)(00|11)(01|10)(00|11)even_0_odd_1 1 even_0_even_1|0(00|11)(01|10)even_0_even_1对于偶数个0和奇数个1构成的串,其第一个字符可能是0或1。1.如果是1,那么剩下的部分一定是偶数个0和偶数个1。2.如果是0,那么经过若干个00或11,一定会出现一个01或10,才能保证0的个数是偶数,1的个数是奇数。若串还没有结束,剩余部分一定是偶数个0和
10、偶数个1。21注意事项正规定义:为了让正规表达式的表示简洁,可以对正规式命名。d1 r1 d2 r2.dn rn各个di的名字都不同每个ri都是d1,d2,di-1 上的正规式 应该写出正规定义或者正则表达式,状态图必须化简223.16 用算法用算法3.3 构造非确定有穷自动机,给出构造非确定有穷自动机,给出处理输入串处理输入串ababbab的状态转换序列:的状态转换序列:23ababbab的状态转换序列24c)(|a)b*)*25ababbab的状态转换序列263.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。a)(a|b)*-closu
11、re(0)=0,1,2,4,7=A-closure(move(A,a)=-closure(3)=1,2,3,4,6,7=B-closure(move(A,b)=-closure(5)=1,2,4,5,6,7=C-closure(move(B,a)=-closure(3)=1,2,3,4,6,7-closure(move(B,b)=-closure(5)=1,2,4,5,6,72728-closure(move(C,a)=-closure(3)=1,2,3,4,6,7-closure(move(C,b)=-closure(5)=1,2,4,5,6,7 则DFA为:3.17 用算法3.2把练习3.
12、16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。-closure(0)=0,1,2,3,4,6,7,8,10,11=A-closure(move(A,a)=-closure(5)=1,2,3,4,5,6,7,8,10,11=B-closure(move(A,b)=-closure(9)=1,2,3,4,6,7,8,9,10,11=C29c)(|a)b*)*-closure(move(B,a)=-closure(5)=1,2,3,4,5,6,7,8,10,11=B-closure(move(B,b)=-closure(9)=1,2,3,4,5,6,7,8,10,11=C-
13、closure(move(C,a)=-closure(5)=1,2,3,4,5,6,7,8,10,11=B-closure(move(C,b)=-closure(9)=1,2,3,4,5,6,7,8,10,11=C则DFA为:30画状态图注意事项应明确地指出开始状态应明确地指出终止状态,不一定只有一个NFA转化为DFA时,NFA的状态集合包含有接受状态,那么对应的DFA状态也是接受状态 313.22 如果两个正规表达式的最少状态如果两个正规表达式的最少状态DFA除状态名以外完除状态名以外完全相同,则这两个正规表达式等价。全相同,则这两个正规表达式等价。(a*|b*)*A:-closure(0)
14、=0,1,2,3,5,6,7,9,10,11,B:-closure(move(A,a)=-closure(4)=1,2,3,4,5,6,7,9,10,11C:-closure(move(A,b)=1,2,3,6,7,8,9,10,113233A状态状态abABCBBCCBC注意事项该题为证明题,做题思路为构造各个正规表达式的最小状态DFA。应该有中间步骤。a)和c)可以见3.17中的解答。343.23 对于下列正规表达式构造最小状态的DFA.解题步骤:1,从正则表达式到NFA2,从NFA到DFA(子集构造法)3,最小化DFA(算法3.6)353.23 对于下列正规表达式构造最小状态的DFA.a
15、)(a|b)*a(a|b)36(b)(a|b)*a(a|b)(a|b)解法一37AstartBabHGaCDaaaEFabaaabbbb最小化DFAa1start2a43babNFAbab)(a|b)a(a|b)(a|b)解法二3820134567aabbaabbstartbaababab图图1.11 接收接收(a|b)a(a|b)(a|b)的的DFA20134567aaba,baabbstart图图1.12 构造构造过过程的第一步程的第一步c)(a|b)a(a|b)(a|b)(a|b)一共有16个状态,满足定理3.23 d)正规表达式(a|b)a(a|b)(a|b)(a|b)共有n-1个(a
16、|b),对应的任何一个DFA至少有2n个状态。证明方法如前图方法所示。39400142233567119101213813141517182119202216startabaaaabbb图:带图:带转移的转移的NFA第一步:第二步A=-closure(0)B=-closure(3,8)C=-closure(5)D=-closure(3,8,10)E=-closure(5,12)F=-closure(3,8,10,15)G=-closure(5,12,17)H=-closure(3,8,15)I=-closure(5,17)J=-closure(3,8,10,15,20)K=-closure(5
17、,12,17,22)41L=-closure(3,8,15,20)M=-closure(5,17,22)N=-closure(3,8,10,20)O=-closure(5,12,22)P=-closure(3,8,20)Q=-closure(5,22)状态状态abABCBDECBCDFGEHIFJKGLMHNOIPQJIKKLMLNOMPQNFGOHIPDEQBC42状态转移表:状态转移表:第三步:应用算法3.6消除状态C之后得到的最少状态DFA:给出奇数个0奇数个1的正规表达式44012311110000start接受奇数个接受奇数个0和奇数个和奇数个1的的的的DFA偶0偶1偶0奇1奇0奇1奇0偶1给出偶数个0和偶数个1的字符串的正规表达式45312011110000start偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1消除状态1:463201110110100start00消除状态2:473011|0010|0101|10start00|11消除状态2:消除状态3:483011|00(10|01)(00|11)*(01|10)startqf(00|11)|(10|01)(00|11)*(01|10)*即:start(11|00)*(01|10)(11|00)*(01|10)(11|00)*(01|10)*(11|00)*奇奇0奇奇13
限制150内