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 5a) 构造一个 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)