清华大学：《编译原理》课程教学资源_复习题1

正规表达式和有穷自动机 1指与出正规式匹配的串 a)(abb)*c与后面的那些串匹配? ababbc abab c babc aaabc b)ab*c*(a|b)c与后面的那些串匹配? acbbc abbcac abc aco c)(a|b)a+(ba)*与后面的那些串匹配? ba bba ababa aa baa 2.为下边所描述的串写正规式,字母表是{0,1} a)以01结尾的所有串 b)只包含一个0的所有串 c)包含偶数个1但不含0的所有串 d)包含偶数个1且含任意数目0的所有串 e)包含01子串的所有串 f)不包含01子串的所有串 3请描述下面正规式定义的串字母表∑={x,y) a)x(xly) b)x*(yx+)*x* c)(xly)*(xx Iyy) (xly) 4.指出哪些串是自动机可接受的 y xyxxy yYy xYyxyxYxy x,y a yyy xxy 5.构造有穷自动机

正规表达式和有穷自动机 1.指与出正规式匹配的串. a) (ab|b)*c 与后面的那些串匹配？ababbc abab c babc aaabc b) ab*c*(a|b)c 与后面的那些串匹配？ acbbc abbcac abc acc c) (a|b)a+(ba)* 与后面的那些串匹配? ba bba ababa aa baa 2. 为下边所描述的串写正规式，字母表是 {0, 1}. a) 以 01 结尾的所有串 b) 只包含一个 0 的所有串 c) 包含偶数个 1 但不含 0 的所有串 d) 包含偶数个 1 且含任意数目 0 的所有串 e) 包含 01 子串的所有串 f) 不包含 01 子串的所有串 3.请描述下面正规式定义的串. 字母表 = {x, y}. a) x(x|y)*x b) x*(yx+)*x* c) (x|y)*(xx|yy) (x|y)* 4. 指出哪些串是自动机可接受的 . a) Xy xyxxy yyyx xyyxyxyxxy b) yyy xx  yyyxy yxxy yx 5. 构造有穷自动机

a)构造一个DFA,接受字母表Σ={0,1}上的以01结尾的所有串 b)构造一个DFA,接受字母表∑={0,1}上的不包含01子串的所有串 c)构造一个NFA,接受字母表∑={x,y}上的正规式x(x1y)*x描述的集合 d)构造一个NFA,接受字母表Σ={0,1}上的正规式(abla)*b+描述的集合并将其 转换为等价的DFA以及最小状态DFA 答案 a)ababbc abab c babc beebe b)acac rebbe abbcac abc eee c)ba bbe ababe aa baa 2注意正规式不唯 c)(11)* d)(0*10*10*) e)(011)*01(01)* a)必须以x开头和x结尾的串 b)每个y至少有一个x跟在后边的串 d)所有含两个相继的x或两个相继的y的串 a)xxxxy xyyxyxyxxy a yyyxy xxy yx 5

a) 构造一个 DFA，接受字母表 = {0, 1}上的以 01 结尾的所有串 b) 构造一个DFA，接受字母表 = {0, 1}上的不包含01 子串的所有串. c) 构造一个NFA，接受字母表 = {x,y}上的正规式x(x|y)*x描述的集合 d) 构造一个NFA，接受字母表 = {0,1}上的正规式(ab|a)*b+描述的集合并将其 转换为等价的DFA.以及最小状态DFA 答案 1. a) ababbc abab c babc aaabc b) acac acbbc abbcac abc acc c) ba bba ababa aa baa 2.注意 正规式不唯一 a) (0|1)*01 b) 1*01* c) (11)* d) (0*10*10*)* e) (0|1)*01(0|1)* f) 1*0* 3. a)必须以 x 开头和x结尾的串 b) 每个 y 至少有一个 x 跟在后边的串 d) 所有含两个相继的x或两个相继的y的串 4. a) xy xyxxy yyyx xyyxyxyxxy c) yyy xx  yyyxy yxxy yx 5． b)

NF DFA NFA: DFA b Mini dfa b

c) Mini. DFA