. 1.构造正规式的DFA。 （1）1(0|1)*101
首先构造NFA：
ε 1 X A
NFA化为DFA： 状态转换表：
Q {X} A {ABC} B {BCD} C {BC} D {BCE} E {BCDY} Y
状态转换图：
A 1 初态
A B C D E Y 化简后得：
A 1 B 0
0 B 1 ε C 1 D 0 E 1 Y 1 {ABC} B {BCD} C {BCD} C {BCD} C {BCDY} Y {BCD} C 1 0 C B 1 0 D 0 1 B C C C Y C 0 1 1 C 0 E1 0 1 Y 0 D E D D E 1 1 0 Y E 1 0 {BC} D {BCE} E {BC} D {BC} D {BCE} E 0 1 / 19
. （2）(a|b)*(aa|bb)(a|b)*
a
ε ε
X 1 b ？ NFA化为DFA：
Q {X 1 2} {1 2 3} {1 2 4} {1 2 3 5 Y} {1 2 4 5 Y} {1 2 4 Y} {1 2 3 Y} 3 a 2 b 4 b a 5 ε a Y b a {1 2 3} {1 2 3 5 Y} {1 2 3} {1 2 3 5 Y} {1 2 3 Y} {1 2 3 Y} {1 2 3 5 Y} {1 2 4} {1 2 4 } {1 2 4 5 Y} {1 2 4 Y} {1 2 4 5 Y} {1 2 4 5 Y} {1 2 4 Y} b a 所以，DFA为： a a b 1 3 X a a b b b b 2 4 a b 化简得： a 1 a a a b X Y b b 2
b
2 / 19
5 b a 6 . 0 （3）（0|11*0）* ε X A 1
B
ε
C
1 NFA到DFA：
Q {X A Y} X {B C D} A {A Y} B {C D} Y 1 X 0
化简后得； 0 X
ε 0 D ε Y 1 {B C D} A {C D} Y {B C D} A {C D} Y 0 {A Y} B {A Y} B {A Y} B {A Y} B A 1 0 B 0 1 1 Y 0 1 0 A 1 3 / 19
. 2.将下图确定化和最小化。
a a
0 1 a,b
解: 首先取A=ε-CLOSURE({0})={0},NFA确定化后的状态矩阵为:
A B C Q’ {0} {0,1} {1} a {0,1} {0,1} {0} b {1} {1} NFA确定化后的DFA为：
a a AB a bb
C
将A,B 合并得:
ab AC a
4 / 19
. 3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。
解：按题意相应的正规表达式是0*(0 | 10)*0*
构造相应的DFA，首先构造NFA为
0 0 0
εεεεY X 0 1 3
1 0
2
用子集法确定化 I {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} I0 {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} I1 {2} {2} / {2} S 1 2 3 4 0 2 2 4 4 1 3 3 3
DFA为
0
1 02
1 1 0
1 4
3 0
5 / 19
. 4.给出NFA等价的正规式R。 方法一：首先将状态图转化为
ε X 1 1 A B ε C 消去 Y 得
B
ε 11 ε X 、
*（0|1）11 X 0,1
消去其余结点 A C 0，1 Y Y NFA等价的正规式为（0|1）*11
方法二：NFA→右线性文法→正规式 A→0A|1A|1B B→1C C→ε
A=0A+1A+1B B=1
A=0A+1A+11
A=(0+1)*11→(0|1)*11
6 / 19
. 5.试证明正规式（a|b）*与正规式（a*|b*）*是等价的。
证明： (1)
X 正规式(a|b)的NFA为=>εε b
{1,y} a {1,y} b {1,y} {1,y} {X, 1,y} {1,y} a
其最简DFA为 *
a 1 Y =>
b
A
(2)正规式（a*|b*）*的 NFA为： a
其最简化DFA为： 3 a εε
=> X εε=> 1
εεb
Y A b
DFA的状态转换表： {x,1,2,3,y} {1,2,3,y}
由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*。
7 / 19
a {1,2,3,y} {1,2,3,y} b {1,2,3,y} {1,2,3,y} 2 .
6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b|ab)*。
（1） 试构造状态最小化的DFA M，使得L（M）=L（R）。 （2） 求右线性文法G，使L（G）=L（M）。 解:(1)构造NFA:
6 b X ε 1 b ε 2 a 3 b 4 ε 5 a ε Y b (2)将其化为DFA,转换矩阵为:
Q {X,1,2} 1 {3} 2 {1,2} 3 {4,5,Y} 4 {6} 5 {5,Y} 6
8 / 19
{3} 2 {6} 5 {6} 5 a {3} 2 b {1,2} 3 {4,5,Y} 4 {1,2} 3 {5,Y} 6 {5,Y} 6 {5,Y} 6 .
2 a 1 b 3 b a b 4 a 5 b b 6 b a 再将其最小化得:
a X
b W b a Y b
（2）对应的右线性文法G=（{X,W,Y},{a,b},P,X） P: X→aW|bXW→bY|b y→aW|bY|b
9 / 19
.
3.8文法G[〈单词〉]为：
〈单词〉-〉〈标识符〉|〈整数〉
〈标识符〉-〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉 〈整数〉-〉〈数字〉|〈整数〉〈数字〉 〈字母〉-〉A|B|C 〈数字〉|->1|2|3
（1）改写文法G为G’，使L(G’)=L(G)。 （2）给出相应的有穷自动机。
解：（1）令D代表单词，I代表标识符，Z代表整数，有G’（D）：
D→I | Z
I→A | B | C | IA | IB | IC | I1 | I2 | I3 Z→1 | 2 | 3 | Z1 | Z2 | Z3 (2)左线性文法G’所对应的有穷自动机为：
M=({S,D,I,Z},{1,2,3,A,B,C},f,S,{D}) f: f(S,A)=I, f(S,B)=I, f(S,C)=I f(S,1)=Z f(S,2)=Z f(S,3)=Z
f(I,A)=I f(I,B)=I f(I,C)=I
10 / 19
. f(I,1)=I f(I,2)=I f(I,3)=I f(I, ε)=I f(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, ε)=D
3.10给出下述文法所对应的正规式。
S→0A|1B A→1S|1 B→0S|0
解: 相应的正规式方程组为：
S=0A+1B ① A=1S+1 ② B=0S+0 ③
11 / 19
. 将②，③代入①，得 S=01S+01+10S+10 ④
对④使用求解规则，得 (01|10)* （01|10）为所求。
3.4给出文法G[S]，构造相应最小的DFA。
S->aS|bA|b A-> aS
方法一： S=aS+bA+b A=aS
S=aS+baS+b S=(a+ba)*b
即：S=(a|ba)*b
12 / 19
. 正规式(a|ba)*b对应的NFA： a
ε ε X 1 2
a b
3
正规式(a|ba)*b对应的DFA：
Q {X 1 2} X {1 2 } 1 {3Y} Y a b Y b {3Y} Y {3 Y} Y {1 2} 1 {1 2} 1 {1 2} 1
a
a 1 b a X Y
b
化简后： a a X Y b
方法二：P43 右线性正规文法到有穷自动机的转换。
文法S->aS|bA|b
A-> aS 对应的NFA为：
M=({S,A,D},{a,b},f,{S},{D})
其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S
其NFA图为：
a
S bA a
13 / 19
. b
D
NFA确定化后的状态矩阵为:
1 2
NFA确定化后的DFA为： ab 12 a
Q’ {S} {A,D } a {S} {S} φ b { A,D} 3.5给出下述文法所对应的正规式：
S->aA
A->bA+aB+b B->aA
解：将文法改为：
S=aA①
A=bA+aB+b② B=aA ③ 将③代入②，得
14 / 19
. A=bA+aaA+b ④将④用求解规则，得
**
A= (b|aa)b ⑤,带入①得，S= a(b|aa)b,
*
故文法所对应的正规式为R= a(b|aa)b。
3.6给出与下图等价的正规文法G。
a
AaBb C b ab D b
答: 该有穷自动机为:
M=({A,B,C,D},{a,b},f,{A},{C,D})
其中f(A,a)=B, f(A,b)=D, f(B,a)=φ, f(B,b)=C,
f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D
根据其转换规则，与其等价的正规文法G为 G=（{A,B,C,D},{a,b},P,A）,其中
P : A→aB|bD B→bC C→aA|bD|ε D→aB|bD|ε
3.12.解释下列术语和概念：
(1)确定有穷自动机
答：一个确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），
其中：
Q是一个有穷状态集合，每一个元素称为一个状态；
15 / 19
. Σ是一个有穷输入字母表，每个元素称为一个输入字符； f是一个从Q*Σ到Q的单值映射； f（qi,a）=qj (qi,qj∈Q,a∈Σ)
表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj
称为 qi 的一个后继状态。我们说状态转换函数是单值函数，是指 f（qi,a） 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。
S∈Q，是惟一的一个初态； Z 真包含于Q，是一个终态集。
（2）非确定有穷自动机
一个非确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：
Q是一个有穷状态集合，每一个元素称为一个状态； Σ是一个有穷输入字母表，每个元素称为一个输入字符； 状态转换函数是一个多值函数。
f（qi,a）={某些状态的集合}(qi∈Q)，表示不能由当前状态、当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。 S 包含于 A，是非空初态集。 Z 真包含于 Q，是一个终态集。
（3）正规式和正规集
16 / 19
. 有字母表Σ={a1,a2,…an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：
（1）φ是Σ是的正规式，它所表示的正规集是φ，即空集{}。 （2）ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即
{ε} 。
（3）是Σ上的一个正规式，它所表示的正规集是由单个符号ai 所组
成，即{ai}。
（4）e1和e2是Σ是的正规式，它们所表示的正规集分别为L(e1)和
L(e2),则
①e1 | e2是Σ上的一个正规式，它所表示的正规集为 L(e1 | e2)=L(e1)∪L(e2).
② e1e2是Σ上的一个正规式，它所表示的正规集为 L(e1e2)=L(e1)L(e2).
③ (e1)*是Σ上的一个正规式，它所表示的正规集为 L((e1)*)=L((e1))*.
3．1构造下列正规式相应的DFA。
(1) 1 ( 0 | 1)*101
(2) ( a | b )*( aa | bb )( a | b )* (3) (( 0 | 1 )* | ( 11 ))* (4) ( 0 | 11*0 )*
3．2将下面图(a)和(b)分别确定化和最小化. a a
0 1 a,b
17 / 19
. (a)
b ba 02b3 a aa abba 145 b
（b）
3.3构造一个DFA，他接收∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在
右边。
3.4给出文法G[S]，构造相应最小的DFA。 SaS | bA | b AaS 3.5给出下述文法所对应的正规式：
S->Aa
A->bA+aB+b B->aA
3.6给出与下图等价的正规文法G。 a
AaBb C b ab D b
3.7给出与图3.29中的NFA等价的正规式R。 3.8 文法G[〈单词〉]为： 〈单词〉〈标识符〉| 〈整数〉 〈标识符〉〈标识符〉〈字母〉| 〈标识符〉〈数字〉|〈字母〉 〈整数〉〈数字〉|〈整数〉〈数字〉 〈字母〉 A | B | C 〈数字〉1 | 2 | 3 （1） 改写文法G为G’，使L(G’)=L(G). （2） 给出相应的有穷自动机。
3.9试证明正规式（a|b）*与正规式（a*|b*）*是等价的。
18 / 19
. 3．10给出下述文法所对应的正规式： S 0A | 1B A 1S | 1 B 0S | 0
3．11设字母表Σ={a,b}，给出Σ上的正规式R=b*ab(b | ab)*. (1) 试构造状态最小化的DFA M，使得L（M）=L（R）。 (2) 求右线性文法G，使L（G）=L（M）。 3．12解释下列术语和概念。 （1） 确定有穷自动机 （2） 非确定有穷自动机
（3） 正规式和正规集
/ 19
19
