第四章 作业讲解参考答案docx.docx
《第四章 作业讲解参考答案docx.docx》由会员分享，可在线阅读，更多相关《第四章 作业讲解参考答案docx.docx（16页珍藏版）》请在冰点文库上搜索。
第四章作业讲解参考答案docx
第四章作业讲解（参考答案）
1.构造下列正规式相应的DFA。
（1）1（011）*101
（2）1（1010*11（010）*1）*0
（3）a（（a|b）*|ab*a）*b
（4）b（（ab）*|bb）*ab
确定化
0
1
X
A
A
A
AB
AB
AC
AB
AC
A
ABY
ABY
AC
AB
重新命名，令AB为B、AC为C、
ABY为D
0
1
X
A
A
A
B
B
C
B
C
A
D
D
C
B
（2）解：
先构造NFAM
1010*11（010）*1
1（010）*1
再构造状态转换矩阵表:
I
10
II
S
0
1
{X}
{1,2,4}
X
1
{1,2,4}
{y}
{5,9,10,11}
1
Y
2
{5,9,10,11}
{6,12}
{4,2}
2
3
4
{6,12}
{2,4,7,8,13}
3
5
{4,2}
{y}
{5,9,10,11}
4
Y
2
{2.4.7.8.13}
{2,4,8,10,11,y}
{5,9,10,11}
5
6
2
{2,4,}
{2,4,&12,y}
{2,4,5,9,10,11}
6
7
8
{2,4,8,12,y}
{2,4,&y}
{5,9,10,11,13}
7
9
10
{2,4,5,9,10,11}
{6,12,y}
{2,4,5,9,10,11}
8
11
8
{2,4,&y}
{2,4,&y}
{5,9,10,11}
9
9
2
{5,9,10,11,13}
{6,10,11,12}
{2,4}
10
14
4
{6,12,y}
{2,4,7,8,13}
11
5
{6,10,11,12}
{12}
{2,4,7,&13}
14
15
5
{12}
{13}
15
12
{13}
（10,11}
12
13
{10,11}
{12}
{2,4}
13
15
4
（y}
Y
1
⑶解:
E
b
确定化:
la
lb
-S
A
A
AB
AZ
AB
AB
ABZ
+AZ
AB
AZ
+ABZ
AB
ABZ
重新命名，以0、1、2、3、4代替{S},{A},{AB},{AZ},{ABZ}得DFA其中0为初态，3,4为终态。
rz
la
FEZ
1
匚
2
3
FZ
2
2
I
2
I
DFA图省略
确定化省略
3、P72题3,图4.20确定化解：
0
1
S
VQ
QU
VQ
VZ
QU
QU
V
QUZ
VZ
Z
Z
V
QUZ
Z
重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。
0
1
s
A
B
A
C
B
B
D
E
C
F
F
D
F
E
C
E
F
F
F
（b）化简下列DFA为最小化。
Vn与Vt分开
只有4输入a进0,其他不会。
2输入a进1,1,3,5输入a进本身。
P3=«0）,{4},{2},{3},{1,5}）1,5输入b进4,3输入b进2。
所以，1和5是等价的点。
DFA如下:
D
如果改为:
结果为：
Po=（{0,1}，{2,3,4,5}）Vn与Vt分开
Pi=（{0,1},{2,4},{3,5}）
5、构造一个DFA,它接受》={0,1}上所有满足如下条件的字符串：
每个1都有0直接跟在右边，并写出相应的正规式和正规文法。
解：
按题意相应的正规表达式是0*（0I10）*0*或0*（100*）*0*
构造相应的DFA,首先构造NFA为
用子集法确定化
I
Io
Ii
s
0
1
{X,0,l,3,Y}
{0丄3,丫}
{2}
1
2
3
{0,l,3,Y}
{0丄3,Y}
{2}
2
2
3
⑵
{1,3,Y}
/
3
4
{1,3,Y}
{1,3,Y}
{2}
4
4
3
DFA为
可最小化,终态组为{1,2,4},非终态组为{3},{l,2,4}（）u{1,2,4},{1,2,4}】u{3},所以1,2,4为等价状态，可合并。
相应正规文法:
S^OSls
S-*1A
A—OS
7、对以下文法构造相应最小的DFA
S-*aA|bQ
A-*aA|bB|b
B-*bD|aQ
Q-*aQ|bD|b
D-*bB|aA
E-*aB|bF
F-*bD|aE|b
解：
1）化简文法，E和F是不可到达的，应删除。
文法为:
S-*aA|bQ
A-*aA|bB|b
B-*bD|aQ
Q-*aQ|bD|b
D-*bB|aA
2）按正规文法到NFA转化方法，得到下图NFA：
3）对NFA确定化，再最小化。
得DFA如下:
8、给出下述文法所对应的正规式:
S—0AI1B
A-1S|1
B-OS|O
解：
SnOAnOl〜
SnOAnOlS
SnlBnlO
SnlEnlOS丿
SnOlIlO
SnOlSIlOS
0（01）*1（10）*
因此，Sn（01+10）+
正规式：
L（S）=（01|10）+
PO=（{6,7},{1,2,3,4,5}）
PO=（{6,7},{1,2},{3,4,5}）输入b进入不同状态。
PO=（{6,7},{1,2},{3,4},{5}）3,4对d有定义,5没有定义
最小化DFA如下：
正规式为：
b*a（clda）*bb*
10、构造下述文法G[S]的自动机：
S-A0
A-A0IS1I0
解：
SnAOnOO
SnAOnAOOnOOO
S=>...=>00
SnAOnSlOnAOlOnOOlO
SnAOnAOOnSlOOnAOlOOnS10100nA010100=0010100
得出相应正规式：
L（G（S）={（OI1）+,且由00开头，每一个1后面至少有
一个0}
12、证明下列正规表达式是等价的（用DFA方法）
①（alb）*
a
③（（sla）b*）*
升级会员 