编译原理第4章答案精编版.docx
《编译原理第4章答案精编版.docx》由会员分享，可在线阅读，更多相关《编译原理第4章答案精编版.docx（19页珍藏版）》请在冰点文库上搜索。
编译原理第4章答案精编版
第四章词法分析
1构造下列正规式相应的DFA
（1）1（0⑴*101
（2）1（1010*|1（010）*1）*0
（3）a（（a|b）*|ab*a）*b
（4）b（（ab）*|bb）*ab
解：
（1）1（0|1）*101对应的NFA为
（2）1（1010
1
1
£
0
£
F表由子集法将NFA转换为DFA
I
10=&closure（MoveTo（l,0））
I1=&closure（MoveTo（l,1））
A[0]
B[1]
B[1]
B[1]
C[1,2]
C[1,2]
D[1,3]
C[1,2]
D[1,3]
B[1]
E[1,4]
E[1,4]
B[1]
B[1]
F表由子集法将NFA转换为DFA
I
10=&closure（MoveTo（l,0））
I1=&closure（MoveTo（l,1））
A[0]
B[1,6]
B[1,6]
C[10]
D[2,5,7]
C[10]
D[2,5,7]
E[3,8]
B[1,6]
E[3,8]
F[1,4,6,9]
F[1,4,6,9]
G[1,2,5,6,9,10]
D[2,5,7]
G[1,2,5,6,9,10]
H[1,3,6,9,10]
I[1,2,5,6,7]
H[1,3,6,9,10]
J[1,6,9,10]
K[2,4,5,7]
I[1,2,5,6,7]
L[3,8,10]
I[1,2,5,6,7]
J[1,6,9,10]
J[1,6,9,10]
D[2,5,7]
K[2,4,5,7]
M[2,3,5,8]
B[1,6]
L[3,8,10]
F[1,4,6,9]
M[2,3,5,8]
N[3]
F[1,4,6,9]
N[3]
O[4]
O[4]
P[2,5]
P[2,5]
N[3]
B[1,6]
|aba）b（
|bb）ab（
（3）a（（a|b）
（4）b（（ab）
2•已知NFA=（{x,y,z},{0,1},M,{x},{z}M（y,1）=$,M（z,1）={y},构造相应的解：
根据题意有NFA图如下
）其中:
M（x,0）={z},M（y,0）={x,y},M（z,0）={x,z},M（x,1）={x},
DFA
n
F表由子集法将NFA转换为DFA
I
10=&closure（MoveTo（l,0））
I1=&closure（MoveTo（l,1））
A[x]
B[z]
A[x]
B[z]
C[x,z]
D[y]
C[x,z]
C[x,z]
E[x,y]
D[y]
E[x,y]
E[x,y]
F[x,y,z]
A[x]
F[x,y,z]
F[x,y,z]
E[x,y]
110
1
F面将该DFA最小化：
（1）首先将它的状态集分成两个子集：
Pi={A,D,E},P2={B,C,F}
（2）区分P2：
由于F（F,1）=F（C,1）=E,F（F,0）=F并且F（C,O）=C,所以F,C等价。
由于F（B,O）=F（C,O）=C,F（B,1）=D,F（C,1）=E,而D,E不等价（见下步），从而B与C,F可以区分。
有P21={C,F},P22={B}。
（3）区分P1：
由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有Pn={A,E},P12={D}
（4）由于F（A,0）=B,F（E,0）=F,而B,F不等价，所以A，E可以区分。
（5）综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。
所以最小化的DFA如下：
3•将图4.16确定化:
解:
0,
I
10=&closure（MoveTo（l,0））
I1=&closure（MoveTo（l,1））
A[S]
B[Q,V]
C[Q,U]
B[Q,V]
D[V,Z]
C[Q,U]
C[Q,U]
E[V]
F[Q,U,Z]
D[V,Z]
G[Z]
G[Z]
E[V]
G[Z]
F[Q,U,Z]
D[V,Z]
F[Q,U,Z]
G[Z]
G[Z]
G[Z]
n
0,
4.把图4.17的⑻和（b）分别确定化和最小化:
（b）
解：
（a）：
A，然后删除B所在的行。
）
（a2）最小化的DFA
（al）确定化的DFA
（b）:
该图已经是DFA下面将该DFA最小化：
（6）首先将它的状态集分成两个子集：
Pi={O},P
（7）区分P2:
由于F（4,a）=0
P21={4},P22={1,2,3,5}。
（8）区分P22：
由于F（1,b）=F（5,b）=4
P221={1,5},P222={2,3}。
2={1,2,3,4,5}
属于终态集，而其他状态输入
属于P21,而F（2,b）与F（3,b）
a后都是非终态集，所以区分F2如下：
P>1，所以区分P22如下
不等于4,即不属于
下表由子集法将NFA转换为DFA
I
la=gclosure（MoveTo（l,a））
Ib=&closure（MoveTo（l,b））
A[0]
B[0,1]
C[1]
B[0,1]
B[0,1]
C[1]
C[1]
A[0]
可得图（a1），由于F（A,b）=F（B,b）=C,并且F（A,a）=F（B,a）=B,所以A,B等价，可将DFA最小化，即：
删除
B,将原来引向B的引线引向与其等价的状态A,有图（a2）。
（DFA的最小化，也可看作将上表中的B全部替换为
b
1
5•构造一个DFA它接收艺={0,1}上所有满足如下条件的字符串：
每个该语言的正则文法。
解：
根据题意，DFA所对应的正规式应为：
（0|（10））*。
所以，接收该串的
都有0直接跟在右边。
然后再构造
NFA如下:
£
0
1
F表由子集法将NFA转换为DFA
I
10=&closure（MoveTo（l,0））
I1=&closure（MoveTo（l,1））
A[0]
B[0,2]
C[1]
B[0,2]
B[0,2]
C[1]
C[1]
B[0,2]
0
显然，A,B等价，所以将上述DFA最小化后有:
0
0
对应的正规文法为：
G[A]:
A1C|0A|£
C0A
6•设无符号数的正规式为e:
e=dd|dd.dd|.dd|dde（s|&）dd|e（s|&）dd|.dde（s|&）dd|dd.dde（s|&）dd
化简e，画岀e的DFA其中d={0,1,2,…9},s={+,-}
解：
把原正规式的每2,3项，4,5项，6,7项分别合并后化简有：
e=dd|d.dd|de（s|&）dd|d.dde（s|&）dd
=dd*|d*.dd*|（d*|d*.dd*）e（s|e）dd*
最新资料推荐
=（&|d*.|（d*|d*.dd*）e（s|&））dd*
=（&|d*.|d*（&|.dd*）e（s|&））dd*
F面构造化简后的0对应的NFA
n
7•给文法G[S]:
SaA|bQ
AaA|bB|b
BbD|aQ
QaQ|bD|b
DbB|aA
EaB|bF
FbD|aE|b
构造相应的最小的DFA
解：
由于从S岀发任何输入串都不能到达状态E和F,
所以，状态E,F为多余的状态，不予考虑。
这样，可以
写出文法
A
D
Q
G[S]对应的NFA
F表由子集法将NFA转换为DFA
I
Id=£-closure（MoveTo（l,d））
Ie=£-closure（MoveTo（I,e））
Is=£-closure（MoveTo（l,s））
I.=£-closure（MoveTo（I,.））
A[0,1,4,6]:
B[1,7]
C[5,6]
rD[2,6]
B[1,7]
B[1,7]
D[2,6]
C[5,6]
E[7]
F[6]
D[2,6]
G[3,4,7]
E[7]
E[7]
F[6]
E[7]
G[3,4,7]
G[3,4,7]
C[5,6]
F表由子集法将NFA转换为DFA
I
Ia=&closure（MoveTo（l,a））
Ib=&closure（MoveTo（l,b））
i[S]
2[A]
3[Q]
2[A]
2[A]
4[B,Z]
3[Q]
3[Q]
5[D,Z]
4[B,Z]
3[Q]
6[D]
5[D,Z]
2[A]
7[B]
6[D]
2[A]
7[B]
7[B]
3[Q]
6[D]
由上表可知：
（1）因为4,5是DFA的终态，其他是非终态，可将状态集分成两个子集：
Pi={1，2,3，6，7}，P2={4，5}
⑵在Pi中因为2,3输入b后是终态，而1，6，7输入b后是非终态，所以Pi可区分为：
Pii={1，6，7}，Pi2={2，3}
⑶在Pii中由于I输入b后为3,6输入b后为7,而3，7分属Pii和Pi2,所以I与6不等价，同理，I与7不等价。
所以Pii可区分为：
Piii={i}，Pii2={6，7}
⑷查看Pii2={6，7}，由于输入a后为2，3,所以6，7是否等价由2，3是否等价决定。
⑸查看Pi2={2,3}，由于输入b后为4,5,所以2,3是否等价由4,5是否等价决定。
（6）查看P2={4,5},显然4,5是否等价由2,3与6,7是否同时等价决定。
由于有（4）即6,7是否等价由2,3是否等价决定，所以，4,5是否等价由2,3是否等价决定。
由于有（5）即2,3是否等价由4,5是否等价决定，所以有4,5等价，2,3等价,进而6,7也等价。
（7）删除上表中的第3,5,7行，并将剩余行中的3,5,7分别改为对应的等价状态为2,4,6有下表：
I
Ia
Ib
1[S]
2[A]'
2[A]
2[A]
2[A]
4[B,Z]
4[B,Z]
2[A]
6[D]
6[D]
2[A]
6[D]
这样可得最小化的DFA如下:
8•给岀下述文法所对应的正规式:
S0A|1B
A1S|1
B0S|0
解：
把后两个产生式代入第一个产生式有：
S=01|01S
S=10|10S
有:
S=01S|10S|01|10=（01|10）S|（01|10）=（01|10）即:
（01|10）*（01|10）为所求的正规式。
4.18
9•将图
解：
（1）
⑵
⑶
（i）
⑵
⑶
因为
7}。
由于
由于
由于
（01|10）
的DFA最小化，并用正规式描述它所识别的语言:
2
b
b
J1
c
a
x-
b
a
►
4
图4.18
b
b
6,7是DFA的终态，其他是非终态，可将状态集分成两个子集：
P仁{1,2,3,4,5},P2={6,
F（6,b）=F（7,b）=6,而6,7又没有其他输入，所以6,7等价。
F（3,c）=F（4,c）=3,F（3,d）=F（4,d）=5,F（3,b）=6,F（4,b）=7,而6,7等价，所以3,4等价。
F（1,b）=F（2,b）=2,F（1,a）=3,F（2,a）=4,而3,4等价，所以1,2等价。
由于状态5没有输入字符b,所以与1,2,3,4都不等价。
综上所述，上图DFA的状态可最细分解为：
P={{1,2},{3,4},{5},{6,7}}。
b
b
该DFA用正规式表示为:
b*a（c|da）*bb*
10•构造下述文法G[S]的自动机：
SA0
AA0|S1|0
该自动机是确定的吗？
若不确定，则对它确定化。
该自动机相应的语言是什么?
解：
由于该文法的产生式
必须先用代入法得到它对应的正规式。
把
SA0有该文法的正规式：
0（0|01）*0,
SA0,AA0|S1中没有字符集Vt的输入，所以不是确定的自动机。
S
所以，
要将其他确定化，
A0代入产生式AS1有:
A=A0|A01|0=A（0|01）|0=0（0|01）*。
代入
改写该文法为确定的自动机为：
o
0
Y
由于状态A有3次输入0的重复输入，所以上图只是NFA下面将它确定化:
F表由子集法将NFA转换为DFA
I
Io=&closure（MoveTo（l,0））
Ib=&closure（MoveTo（l,1））
A[W]
B[X]
B[X]
C[X,Y,Z]
C[X,Y,Z]
C[X,Y,Z]
B[X]
由上表可知DFA为:
1■:
；A'
0宀.
1
升级会员 