编译原理期末复习题.doc

《编译原理期末复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。(1)有穷自动机接受的语言是正则语言。（）(2)若r1和r2是Σ上的正规式，则r1

2、r2也是。（）(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（）(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a

3、b)*。（）(5)对任何一个NFAM，都存在一个DFAM'，使得L(M')=L(M)。（）(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）答案(1)  T  (2)  T 

4、 (3)  F(4)  F  (5)  T  (6)T3.3 描述下列各正规表达式所表示的语言。(1) 0(0

5、1)*0(2) ((ε

6、0)1*)*(3) (0

7、1)*0(0

8、1)(0

9、1)(4) 0*10*10*10*(5) (00

10、11)*((01

11、10)(00

12、11)*(01

13、10)(00

14、11)*)*答案(1) 以0开头并且以0结尾的，由0和1组成的符号串。(2) {α

15、α∈{0,1}*}(3) 由0和1组成的符号串，且从右边开始数第3位为0。(4) 含3个1的由0和1组成的符号串。 {α

16、α∈{0,1}+，且α中含有3个1}(5)

17、 {α

18、α∈{0,1}*,α中0和1为偶数}3.4 对于下列语言分别写出它们的正规表达式。(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。(3) Σ={0,1}上的含偶数个1的所有串。(4) Σ={0,1}上的含奇数个1的所有串。(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。(6) 不包含子串011的由0和1组成的符号串的全体。(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答案(1) 令Letter表示除这五个元音

19、外的其它字母。   ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2) A*B*....Z*(3) (0

20、10*1)*..(4) (0

21、10*1)*1(5) [分析]设S是符合要求的串，

22、S

23、=2k+1(k≥0）。则S→S10

24、S21，

25、S1

26、=2k(k>0），

27、S2

28、=2k(k≥0）。且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，

29、即S1为：((00

30、11)

31、(01

32、10)(00

33、11)*(01

34、10))*(01

35、10)(00

36、11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：((00

37、11)

38、(01

39、10)(00

40、11)*(01

41、10))*因此，S为：((00

42、11)

43、(01

44、10)(00

45、11)*(01

46、10))*(01

47、10)(00

48、11)*0

49、((00

50、11)

51、(01

52、10)(00

53、11)*(01

54、10))*1(6)1*

55、1*0(0

56、10)*(1

57、ε)(7)接受w的自动机如下：对应的正规表达式：(1(01*

58、0)1

59、0)*3.6 给出接受下列在字母表{0,1}上的语言的DFA。(1) 所有以00结束的符号串的集合。..(2) 所有具有3个0的符号串的集合。答案(a)DFA M=({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*DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定义如下:δ（q0，0）=q1    

60、δ（q0，1）=q0δ（q1，0）=q2    δ（q1，1）=q1δ（q2，0）=q3    δ（q2，1）=q2δ（q3，1）=q3    3.7构造等价于下列正规表达式的有限自动机。(1)10

61、（0

62、11）0*1(2)((0

63、1)*

64、(11))*答案(1)DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定义如下:..(1)δ（q0，0）=q1    δ（q0，1）=q2(2)δ（q1，0）=q1    δ（q1，1）=q3(3)δ（q2，0）=q3    δ（q2，1）=q1(4)(5)(2)DFA M

65、=({0，1}，{q0}，q0，{q0}，δ)(6)其中δ定义如下:(7)δ（q0，0）=q0    δ（q0，1）=q0(8)3.8给定右线性文法G：S->0S

66、1S

67、1A

68、0