4.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串： 每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 [答案]
按题意相应的正规表达式是0*(0 | 10)*0*或
0*( 100*)*0*
构造相应的DFA，首先构造NFA为
用子集法确定化
I I0 I1 S 0 1 {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} DFA：
{0,1,3,Y} {2} 1 2 {0,1,3,Y} {2} 2 2 {1,3,Y} / 3 4 {1,3,Y} {2} 4 4 3 3 / 3
可最小化，终态组为{1,2,4}，非终态组为{3}，
{1,2,4}0 {1,2,4}，{1,2,4}1 {3}， 所以1,2,4为等价状态，可合并。
5．给出下列文法所对应的正规式： S->0A|1B A->1S|1 B->0S|0
[答案]
解方程组S的解：
S=0A|1B A=1S|1 B=0S|0
将A、B产生式的右部代入S中
S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10)
6.为下边所描述的串写正规式，字母表是 {a,b}. a) 以ab 结尾的所有串
b) 包含偶数个b但不含a的所有串
c) 包含偶数个b且含任意数目a的所有串 d) 只包含一个a的所有串 e) 包含ab子串的所有串 f) 不包含ab子串的所有串 [答案]
注意 正规式不唯一 a) (a|b)*ab b) (bb)*
c) (a*ba*ba*)* d) b*ab*
e) (a|b)*ab(a|b)* f) b*a*
7.请描述下面正规式定义的串. 字母表S = {0，1}. a) 0*(10+)*0*
b) (0|1)*(00|11) (0|1)* c) 1(0|1)*0 [答案]
a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的0或两个相继的1的串 c) 必须以 1 开头和0结尾的串
8. 构造有穷自动机.
a) 构造一个DFA，接受字母表??? {0, 1}上的以01 结尾的所有串
b) 构造一个DFA，接受字母表??? {0, 1}上的不包含01 子串的所有串. c) 构造一个NFA，接受字母表??? {x,y}上的正规式x(x|y)*x描述的集合
d) 构造一个NFA，接受字母表??? {a, b}上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA [答案]
b)
c)
9. 设有如图所示状态转换图，求其对应的正规表达式。
[答案]
可通过消结法得出正规式
R=(01)*((00|1)(0|1)*|0)
也可通过转换为正则文法，解方程得到正规式。
10. 已知正规式：
(1)((a|b)*|aa)*b； (2)(a|b)*b.
试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。
[分析]
基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA，如这两个最小DFA一样，也就证明了这两个正规式是等价[答案]
状态转换表1 a 1234 1234 1234 b 124Y 124Y 124Y X124 1234 124Y
状态转换表2 1 2 3 a 2 2 2 B 3 3 3 由于2与3完全一样，将两者合并，即见下表 1 2 a 2 2 b 3 3