编译原理第一次作业参考答案 一、 下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？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组成的字符串.说明：答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”.二、 设字母表=a,b，用正则表达式（只使用a，b，e，|，*，+，？）描述下列语言：1. 不包含子串ab的所有字符串.b*a*2. 不包含子串abb的所有字符串.b*(ab?)*3. 不包含子序列abb的所有字符串.b*a*b?a*注意：关于子串（substring）和子序列（subsequence）的区别可以参考课本第1
