第二、三章习题讲

1、2008-10-282.1 考虑下面的上下文无关文法：S SS+ | SS* |a试说明如何使用该文法生成串aa+a*。试为aa+a*构造一个分析树。该文法产生的语言是什么？ANSWER:S SS* SS+S* aa+a*图以a为变量，+和*为二元操作符的后缀表达式22.2 下面的文法产生什么语言？S0S1|010n1n（n=1,2,） S+SS|-SS|a以a为变量，+和-为二元操作符的前缀表达式SS(S)S|括号的匹配SaSbS|bSaS| 由相同数目的a、b组成的字符串，或者空串。3Sa|S+S|SS|S*|(S)以a为数据元素，具有合并、连接、闭包和括号操作符的表达式。a是表达式，若S

2、是表达式则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 abaSbS ababS abab lm lm lm lm

3、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；/*返回整数i和j的最大者*/retu

4、rn ij? i:j；9词素记号属性intintmaxid指向符号表max条目的指针(标点符号左括号iid指向符号表i条目的指针,标点符号逗号jid指向符号表j条目的指针)标点符号右括号;标点符号分号returnreturn操作符大于号?操作符问号:操作符冒号标点符号右大括号标点符号左大括号10注意事项记号token（终结符），模式pattern，词素lexeme（源程序的字符序列）可构成token（记号）的：关键字，操作符，标识符，常量，字符串，标点符号每个词素都要一一记录注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。 不是每个token都要有属性1112(a) 0 ( 0

5、 | 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组成的符号串全

6、体.带有偶数个a和偶数个b的符号串全体.( (aa|bb) | (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

7、| B)* ( c | C)*.( z | Z)*1617 d)没有重复出现的数字的数字符号串全体. 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)* (

8、 ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E h) 不包含子串011的由0和1组成的符号串全体. 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和偶数个

9、1构成的串。另外，和该正规式等价的正规式有( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 。更简单的描述( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 它是基于这样的考虑，满足要求的最简单的串有三种形式（空串除外）：1002113(01 | 10) (00 | 11) (01 | 10)它们任意多次的重复构成的串仍然满足要求。20写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。even_0_even_1 (00 | 11) ( (01 | 10) (00 | 11) (01 | 10

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，那么剩下的部分一定是偶数个0和偶数个1。如果是0，那么经过若干个00或11，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。21注意事项正规定义：为了让正规表达式的表示简洁，可以对正规式命名。 d1 r1 d2 r2 . . . dn rn各个di的名字都不同每个ri都是d1, d2, , di-1 上的

11、正规式 应该写出正规定义或者正则表达式，状态图必须化简223.16 用算法用算法3.3 构造非确定有穷自动机，给出构造非确定有穷自动机，给出处理输入串处理输入串ababbab的状态转换序列：的状态转换序列：23ababbab的状态转换序列24c) (|a)b*)*25ababbab的状态转换序列263.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。(a|b)*-closure(0) = 0,1,2,4,7 = A-closure(move(A,a) = -closure(3) = 1,2,3,4,6,7 = B-closure(move(A

12、,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.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。-closure(0) = 0,1,2

13、,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-closure(move(C,a) = -closure(5) = 1,

14、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) = 0,1,2,3,5,6,7,9,10,11,B:

15、-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) (a|b)*a(a|b)36(

16、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

17、(a | b) (a | b) (a | b)共有n-1个(a | 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=

18、-closure(5,17) J= -closure(3,8,10,15,20) K= -closure(5,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