编译原理第3章课后习题答案.pdf

编译原理第2版参考习题答案 （3章） 第3章 词法分析 3.2.2 试描述下列正则表达式定义的语言 (1)a( a|b )*a 答: {aa, aaa, aba, aaaa, aaba, abaa, abba, ... }, （按穷举法） 或以a开头和结尾，长度大于等于2的a,b串 （自然语言描述） （2） （（ε|a)b*））* 答: 由a和b组成的任意符号串 （3）（a|b）* a(a|b)(a|b) 答: 倒数第3个符号为a 的长度大于等于3的a,b 串 （4）a*ba*ba*ba* 答: 有且仅有三个b 的由a和b构成的所有串的集合。 3.2.5 : 试写出下列语言的正则定义： （1）包含5个元音的所有小写字母串，这些串中的元音按顺序出现 e.g. :{ aeiou, xaxeiou, xaxabcxeeiioouu... } consonant - [b-df-hj-np-tv－z] ctnvowels-(consonant*)(((a+)(consonant*))+)(((e+)(consonant*))+) (((i+)(consonant*))+)(((o+)(consonant*))+)(((u+)(consonant*))+) 注：consonant为除五元音外的小写字母，记号ctnvowels对应的定义即为题目要求的正则 定义。 (2)所有由按字典顺序递增序排列的小写字组成的串。 a*b*……z* （3)注释，即/*和*/之间的串，且串中没有不在双引号（“）中的*/。 head——/* tail ——*/ incomment-(~(*/)| “.”)* * comment-head incomment tail （9）所有由a和b组成且不含有子串abb的串。 * * A-b (a︱ab) 3.3.1给出3.2.2中正则表达式所描述的语言的状态转换图。 (1)a( a|b )*a的状态转换图如下： （2） ε b ε a （3） 4 a a 2 a 5 start a b 0 1 b a 6 b 3 b 7 （4）a*ba*ba*ba* a a a a b b