正规表达式和有穷自动机
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，接受字母表b) 构造一个DFA，接受字母表c) 构造一个NFA，接受字母表d) 构造一个NFA，接受字母表换为等价的DFA.以及最小状态DFA
答案
1.
a) ababbc abab c babc aaabc
{0, 1}上的以01 结尾的所有串
上的不包含01 子串的所有串.
上的正规式x(x|y)*x描述的集合
上的正规式(ab|a)*b+描述的集合并将其转
{0, 1} {x,y} {0,1}
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)
c)
Mini. DFA
