正规表达式和有穷自动机
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,指出哪些串是自动机可接受的
.
Xy xyxxy yyyx xyyxyxyxxy

b) yyy xxyyyxy yxxy 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.注意 正规式不唯一
(0|1)*01
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
yyy xxyyyxy yxxy yx
5．

b)

c)


Mini,DFA