《编译原理期末复习题汇总》由会员分享，可在线阅读，更多相关《编译原理期末复习题汇总（25页珍藏版）》请在金锄头文库上搜索。
1、3.2是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。(1)有穷自动机接受的语言是正则语言。（）(2)若r1和r2是上的正规式，则r1|r2也是。（）(3)设M是一个NFA，并且L(M)x,y,z，则M的状态数至少为4个。（） (4)令a,b，则上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（）(5)对任何一个NFA M，都存在一个DFA M，使得L(M)=L(M)。（）(6)对一个右线性文法G，必存在一个左线性文法G，使得L(G)=L(G)，反之亦然。（）答案(1)T (2)T (3)F(4)F (5)T (6) T3.3描述下列各正规表达式所表示的语言。(1)0(
2、0|1)*0(2)(|0)1*)*(3)(0|1)*0(0|1)(0|1)(4)0*10*10*10*(5)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案(1)以0开头并且以0结尾的，由0和1组成的符号串。(2)|0,1*(3)由0和1组成的符号串，且从右边开始数第3位为0。(4)含3个1的由0和1组成的符号串。 |0,1+，且中含有3个1 (5)|0,1*,中0和1为偶数3.4对于下列语言分别写出它们的正规表达式。 (1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3)=
3、0,1上的含偶数个1的所有串。(4)=0,1上的含奇数个1的所有串。(5)具有偶数个0和奇数个1的有0和1组成的符号串的全体。(6)不包含子串011的由0和1组成的符号串的全体。(7)由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答案(1)令Letter表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2)A*B*.Z*(3)(0|10*1)*(4)(0|10*1)*1(5)分析设S是符合要求的串，|S|=2k+1 (k0）。则 SS10|S21，|S1|=2k (k0），|
4、S2|=2k (k0）。且S1是0,1上的串，含有奇数个0和奇数个1。S2是0,1上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|
5、11)*(01|10)*1(6)1*|1*0(0|10)*(1|)(7)接受w的自动机如下：对应的正规表达式：(1(01*0)1|0)*3.6给出接受下列在字母表0,1上的语言的DFA。(1)所有以00结束的符号串的集合。(2)所有具有3个0的符号串的集合。答案(a) DFAM=(0，1，q0，q1，q2，q0，q2，)其中定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q0（q2，0）=q2 （q2，1）=q0(b)正则表达式: 1*01*01*01* DFAM=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:（q0，0）=q1 （q0，1）=
6、q0（q1，0）=q2 （q1，1）=q1（q2，0）=q3 （q2，1）=q2（q3，1）=q3 3.7构造等价于下列正规表达式的有限自动机。(1)10|（0|11）0*1(2)(0|1)*|(11)*答案(1) DFAM=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:(2) （q0，0）=q1 （q0，1）=q2(3) （q1，0）=q1 （q1，1）=q3(4) （q2，0）=q3 （q2，1）=q1(5) (6) (2) DFAM=(0，1，q0，q0，q0，)(7) 其中定义如下:(8) （q0，0）=q0 （q0，1）=q0(9)3.8 给定右线性文法G：S-0S|
7、1S|1A|0BA-1C|1B-0C|0C-0C|1C|0|1试求一个于G等价的左线性文法G3.9 试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)* 3.10 转换练习3.9中的每个 NFA 为 DFA 。并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。3.11 试把练习3.10中得到的DFA的状态给以最小化。答案(1),(2),(3)的DFA M相同，化简结果为：(4)3.12 我们可以证明两个正规表达式是等价的，如果
8、它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)*答案根据3.11的结果知这几个正规表达式是等价的。3.13 对于下列正规表达式构造最小状态的DFA。(1) (a|b)*a(a|b)(2) (a)b)*a(a|b)(a|b)5对如下文法：GS ：S a b S | a a B | a d B b b B | b 分别给出句子abaabbb和ad的句柄 句子ad的语法分析树为：S a d句子abaabbb的语法分析树为:SabSaaB b b B b所以句子abaabbb的句柄是b
9、；句子ad的句柄是ad .二、（10分）说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。 GA：A B e B B b | a 文法中有左递归，不是LL(1)文法。 转换为 G ： A B e B a B Bb B | Predict(A B e) = a Predict(B a B) = a Predict(Bb B) = b Predict(B ) = e LL(1)分析表: a b e A B e B a B B b B 4. 给出识别正则表达式(（a|bc）*d)+的NFA 。 5已知文法GS：S S；GG G G(T) HH a
10、(S)T T+S S找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。 短语: a, T+S, a(T+S) , H , a(T+S);H , (S) 简单短语：a , T+S , H , (S) 句柄是 a . 6已知文法GS为：SAB | bC Ab | BaD | CAD | b DaS | c 对其每一个非终级符求First集和Follow集。 First (S) = b , a , First (A) = b , First (B) = a , First (C) = b , a , c First (D) = a , c Follow (S) = # Follow (A)
11、= a , c , # Follow (B) = # Follow (C) = # Follow (D) = # 二、（10分）设有文法GA: A iB*e B SB|e S eC|.i C eC|e判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 先计算各个产生式的Predict集： Predict (A- iB*e)= i ; Predict (B- SB) = , . Predict (B-e ) = * Predict (S-eC) = Predict (S-. i) = . Predict (C- eC) = e Predict (C-e ) = 因为Predict集没有冲突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A- iB*e - e B -S B -S B S -e C -. i C -eC - e1、证明下面文法是LL(1)的但不是SLR(1)文法SAaAb|BbBa A B
