编译原理 作业答案

1、编译原理 作业答案 计算机科学系 2010春季学期 编译原理第一次作业参考答案 一、 下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？ 1. b*(ab*ab*)* 所有含有偶数个a的由a和b组成的字符串. 2. c*a(a|c)*b(a|b|c)* | c*b(b|c)*a(a|b|c)* 答案一：所有至少含有1个a和1个b的由a，b和c组成的字符串. 答案二：所有含有子序列ab或子序列ba的由a，b和c组成的字符串. 说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”. 二、

2、设字母表=a,b，用正则表达式（只使用a，b，?，|，*，+，？）描述下列语言： 1. 不包含子串ab的所有字符串. b*a* 2. 不包含子串abb的所有字符串. b*(ab?)* 3. 不包含子序列abb的所有字符串. b*a*b?a* 注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容. ()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 编译原理第二次作业参考答案 一、 考虑以下nfa： 1. 这一nfa接受什么语言（用自然语言描述）？ 所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串. 2. 构造接受

3、同一语言的dfa. 答案一（直接构造通常得到这一答案）： 1 计算机科学系 2010春季学期 答案二（由nfa构造dfa得到这一答案）： 二、 正则语言补运算 3. 画出一个dfa，该dfa恰好识别所有不含011子串的所有二进制串. 1. 画出一个dfa，该dfa恰好识别所有不含011子串的所有二进制串. 2 计算机科学系 2010春季学期 规律：构造语言l的补语言l的dfa，可以先构造出接受l的dfa，再把这一dfa的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别l的dfa. 说明：在上述两题中的d状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”. 在

4、画dfa时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出. 2. 再证明：对任一正则表达式r，一定存在另一正则表达式r，使得l(r)是l(r)的补集. 证明：根据正则表达式与dfa的等价性，一定存在识别语言l(r)的dfa. 设这一dfa为m，则将m的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的dfa m. 易知m识别语言l(r)的补集. 再由正则表达式与dfa的等价性知必存在正则表达式r，使得l(r)是l(r)的补集. 三、 设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释 禁止嵌套. 1. 请给

5、出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串. 书写正则表达式时， 要求仅使用最基本的正则表达式算子（?，|，*，+，？）. 参考答案一：/o(o*z|/)*o+/ 思路：基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o. 参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：/o/*(z/*|o)*o/ 2. 给出识别上述正则表达式所定义语言的确定有限自动机（dfa）. 你可根据问题直接构造dfa，不必运用机 械的算法从上一小题的正则表达式转换得到dfa. ()/ ()/ ()/ ()/ ()/ ()/ ()/

6、 ()/ 编译原理第三次作业参考答案 一、 考虑以下dfa的状态迁移表，其中0，1为输入符号，ah代表状态： 0 1 3 计算机科学系 2010春季学期 a b c d e f g h b a d d d g f g a c b a f e g d 其中a为初始状态，d为接受状态，请画出与此dfa等价的最小dfa，并在新的dfa状态中标明它对应的原dfa状态的子集. 说明：有些同学没有画出状态h，因为无法从初始状态到达状态h. 从实用上讲，这是没有问题的. 不过，如果根据算法的步骤执行，最后是应该有状态h的. 二、 考虑所有含有3个状态（设为p，q，r）的dfa. 设只有r是接受状态. 至于哪

7、一个状态是初始状态与本问题 无关. 输入符号只有0和1. 这样的dfa总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3=729种可能. 在这729个dfa中，有多少个p和q是不可区分的（indistinguishable）？解释你的答案. 解：考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都迁移到p或q（4种可能）. 类似地，在输入符号为1时，也有5种可能使p和q无法区分. 如果再考虑r的迁移，r的任何迁移对问题没有影响. 于是r在输入0和

8、输入1时各有3种可能的迁移，总共有3*3=9种迁移. 因此，总共有5*5*9=225个dfa，其中p和q是不可区分的. 三、 证明：所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言. 证明：用反证法. 假设含有素数个a的字符串组成的集合是正则语言，则必存在一个dfa接受这一语言，设此dfa为d. 由于d的状态数有限，而素数有无限多个，所以必存在两个不同的素数p和q（设p考虑仅含有字母a，长度为p+p(q-p)的字符串t. t从初始状态出发，经过p个a到达状态s，再经过(q-p)个a仍然到达s；同样，经过p(q-p)个a后仍然到达s. 因此，从初始状态出发，经过p+p(q-p)个a后

9、必然到达状态s. 由于p+p(q-p)=p(q-p+1)是合数，而s为接受状态，因而得出矛盾. 原命题得证. ()/ ()/ ()/ ()/ ()/ ()/ ()/ ()/ 4 计算机科学系 2010春季学期 编译原理第四次作业参考答案 一、 用上下文无关文法描述下列语言： 1. 定义在字母表=a, b上，所有首字符和尾字符相同的非空字符串. s ? ata | btb | a | b t ? at | bt | ? 说明： 1. 用t来产生定义在字母表=a, b上的任意字符串； 2. 注意不要漏了单个a和单个b的情况. 2. l=0i1j|ij2i且i0. s ? 0s1 | 0s11 | ? 3. 定义在字母表=0, 1上，所有含有相同个数的0和1的字符串（包括空串）. s ? 0s1 | 1s0 | ss | ? 思路： 分两种情况考虑. 1) 如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有s ? 0s1 | 1s0； 2) 如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此 有s ? s