清华大学-编译原理复习题1.doc

《清华大学-编译原理复习题1.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、正规表达式和有穷自动机1.指与出正规式匹配的串.a)(ab

2、b)*c与后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a

3、b)c与后面的那些串匹配？acbbcabbcacabcaccc)(a

4、b)a+(ba)*与后面的那些串匹配?babbaababaaabaa2.为下边所描述的串写正规式，字母表是{0,1}.a)以01结尾的所有串b)只包含一个0的所有串c)包含偶数个1但不含0的所有串d)包含偶数个1且含任意数目0的所有串e)包含01子串的所有串f)不包含01子串的所有串3.请描述下面正

5、规式定义的串.字母表S={x,y}.a)x(x

6、y)*xb)x*(yx+)*x*c)(x

7、y)*(xx

8、yy)(x

9、y)*4.指出哪些串是自动机可接受的.a)Xyxyxxyyyyxxyyxyxyxxyb)yyyxx¶yyyxyyxxyyx5.构造有穷自动机.a)构造一个DFA，接受字母表S={0,1}上的以01结尾的所有串b)构造一个DFA，接受字母表S={0,1}上的不包含01子串的所有串.c)构造一个NFA，接受字母表S={x,y}上的正规式x(x

10、y)*x描述的集合d)构造一个NFA，接受字母表S={0,1

11、}上的正规式(ab

12、a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA答案1.a)ababbcababcbabcaaabcb)acacacbbcabbcacabcaccc)babbaababaaabaa2.注意正规式不唯一a)(0

13、1)*01b)1*01*c)(11)*d)(0*10*10*)*e)(0

14、1)*01(0

15、1)*f)1*0*3.a)必须以x开头和x结尾的串b)每个y至少有一个x跟在后边的串d)所有含两个相继的x或两个相继的y的串4.a)xyxyxxyyyyxxyyxyxyxxyc)yy

16、yxx¶yyyxyyxxyyx5．b)c)Mini.DFA