编译原理期末复习题.doc

编译原理期末复习题.doc

ID:48208253

大小:417.50 KB

页数:25页

时间:2020-01-22

编译原理期末复习题.doc_第1页
编译原理期末复习题.doc_第2页
编译原理期末复习题.doc_第3页
编译原理期末复习题.doc_第4页
编译原理期末复习题.doc_第5页
资源描述:

《编译原理期末复习题.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。