编译原理 作业答案

编译原理 作业答案

ID:26922611

大小:544.15 KB

页数:11页

时间:2018-11-30

编译原理 作业答案_第1页
编译原理 作业答案_第2页
编译原理 作业答案_第3页
编译原理 作业答案_第4页
编译原理 作业答案_第5页
资源描述:

《编译原理 作业答案》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、计算机科学系2010春季学期《编译原理》第一次作业参考答案一、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)?1.b*(ab*ab*)*所有含有偶数个a的由a和b组成的字符串.2.c*a(a

2、c)*b(a

3、b

4、c)*

5、c*b(b

6、c)*a(a

7、b

8、c)*答案一:所有至少含有1个a和1个b的由a,b和c组成的字符串.答案二:所有含有子序列ab或子序列ba的由a,b和c组成的字符串.说明:答案一要比答案二更好,因为用自然语言描述是为了便于和非专业的人员交流,而非专业人员很可能不知道什么是“子序

9、列”,所以相比较而言,答案一要更“自然”.二、设字母表∑={a,b},用正则表达式(只使用a,b,e,

10、,*,+,?)描述下列语言:1.不包含子串ab的所有字符串.b*a*2.不包含子串abb的所有字符串.b*(ab?)*3.不包含子序列abb的所有字符串.b*a*b?a*注意:关于子串(substring)和子序列(subsequence)的区别可以参考课本第119页方框中的内容.~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦

11、)/~~(≧▽≦)/~《编译原理》第二次作业参考答案一、考虑以下NFA:1.这一NFA接受什么语言(用自然语言描述)?所有只含有字母a和b,并且a出现偶数次或b出现偶数次的字符串.2.构造接受同一语言的DFA.答案一(直接构造通常得到这一答案):11计算机科学系2010春季学期答案二(由NFA构造DFA得到这一答案):一、正则语言补运算1.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串.1.画出一个DFA,该DFA恰好识别所有不含011子串的所有二进制串.11计算机科学系2010春

12、季学期规律:构造语言L的补语言L’的DFA,可以先构造出接受L的DFA,再把这一DFA的接受状态改为非接受状态,非接受状态改为接受状态,就可以得到识别L’的DFA.说明:在上述两题中的D状态,无论输入什么符号,都不可能再到达接受状态,这样的状态称为“死状态”.在画DFA时,有时为了简明起见,“死状态”及其相应的弧(上图中的绿色部分)也可不画出.1.再证明:对任一正则表达式R,一定存在另一正则表达式R',使得L(R')是L(R)的补集.证明:根据正则表达式与DFA的等价性,一定存在识别语言L(R)的DF

13、A.设这一DFA为M,则将M的所有接受状态改为非接受状态,所有非接受状态改为接受状态,得到新的DFAM’.易知M’识别语言L(R)的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’,使得L(R’)是L(R)的补集.一、设有一门小小语言仅含z、o、/(斜杠)3个符号,该语言中的一个注释由/o开始、以o/结束,并且注释禁止嵌套.1.请给出单个正则表达式,它仅与一个完整的注释匹配,除此之外不匹配任何其他串.书写正则表达式时,要求仅使用最基本的正则表达式算子(e,

14、,*,+,?).参考答案一:/o(

15、o*z

16、/)*o+/思路:基本思路是除了最后一个o/,在注释中不能出现o后面紧跟着/的情况;还有需要考虑的是最后一个o/之前也可以出现若干个o.参考答案二(梁晓聪、梁劲、梁伟斌等人提供):/o/*(z/*

17、o)*o/2.给出识别上述正则表达式所定义语言的确定有限自动机(DFA).你可根据问题直接构造DFA,不必运用机械的算法从上一小题的正则表达式转换得到DFA.~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/~~(≧▽≦)/

18、~《编译原理》第三次作业参考答案一、考虑以下DFA的状态迁移表,其中0,1为输入符号,A~H代表状态:0111计算机科学系2010春季学期ABABACCDBDDAEDFFGEGFGHGD其中A为初始状态,D为接受状态,请画出与此DFA等价的最小DFA,并在新的DFA状态中标明它对应的原DFA状态的子集.说明:有些同学没有画出状态H,因为无法从初始状态到达状态H.从实用上讲,这是没有问题的.不过,如果根据算法的步骤执行,最后是应该有状态H的.一、考虑所有含有3个状态(设为p,q,r)的DFA.设只有r是

19、接受状态.至于哪一个状态是初始状态与本问题无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数,因为对于每一状态和每一输入符号,可能迁移到3个状态中的一个,所以总共有3^6=729种可能.在这729个DFA中,有多少个p和q是不可区分的(indistinguishable)?解释你的答案.解:考虑对于p和q,在输入符号为0时的情况,在这种情况下有5种可能使p和q无法区分:p和q在输入0时同时迁移到r(1种可能),或者p和q在输入0时,都

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

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

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