作业评讲
1
77
CH.3.练习题7(P64.)
(3) 正规式 0*10*10*10*
NFA:
0
0
0
0
X ε 1 ε 2 1 3 ε 4 ε 5 1 6 ε 7 ε 8 1 9 ε 10 ε Y
0
001
11
0
21 最小化DFA:
0
0
0 12
2020/4/5
0
0
3
5
1
0
1
4 16
0
1
41
作业评讲
DFA:
依照字典序排列; 正规式 (a|A)*(b|B)*(c|C)*(d|D)*…(z|Z)*
2020/4/5
99
CH.3.练习题9(P64.)
9.问题：没构造出DFA；没过程；方法没掌握。
(1) {0,1}上的含有子串010的所有串; 至少含一个。 正规式 (0|1)*010(0|1)* 或 (0*1*)*010(0*1*)*
{3,2}
{3,4,2}
2 23
{3,4,2} {3,5,2} {3,4,2}
3 43
{3,5,2} {3,2}
{3,Y,4,2}
4 25
{3,Y,4,2} {3,5,2} 2020/4/5
{3,4,2} 作业评讲
终5
4
3 5
5
CH.3.练习题7(P64.) 初始: {0,1,2,3,4}和{5}
解：证明 U|V=V|U
因为 L(U|V)=L(U)∪L(V) =L(V)∪L(U)
=L(V|U)
解：证明 U(VW)=(UV)W
因为 L(U(VW)) =L(U)L(VW)
= L(U)(L(V)L(W))
=(L(U)L(V))L(W)
= L(UV)L(W) = L((UV)W)
2020/4/5
1
0 1 1 12 031 4
I
I0
{0} 初0
0
I1 {1}
0
1 0 11
DFA: 03
{1} {1,2} {1,3}
1 {1} 1 2 {1,3} 3 3 {1} 1
{1,2} 2 {1,2} 2 {1,2,4} 4
1
0 10
2 14
{1,2,4}终4 {1,3} 3 {1,2} 2
2020/4/5
程序设计语言
CH3.词法分析
《程序设计语言编译原理》
陈火旺等编著
2000年第3版
2020题2(P63.)
2. 给出下面C++程序段中的单词符号及其属性值。
int CInt::nMulDiv(int n1,int n2)
{ if (n3 = = 0) return 0;
< ),-> ,
< {, -> ,
2020/4/5
22
CH.3.练习题2(P63.)
续解： < if,-> , < n3, “n3”> , <0, 0> , < return,-> , < ;,-> , < return,-> , < n1, “n1”> , < n2, “n2”> , </, -> , <;,-> ,
左岸---Z；右岸---U;
状态
左:… 右:…
左岸到右岸, 人或人带一件东西 右岸到左岸, 人或人带一件东西
2020/4/5
+ 人,东西
－ 人,东西
12 12
CH.3.练习题10(P64.)
(1) 正规式 1(0|1)*101 ∵{0,1,2,3,4}0={2,4}
DFA:
0
2
0
04
{0,1,2,3,4}1={1,3,5} ∴划分为{0,1,2,3}和{4}
0 11
1 0 1 0 ∵{0,1,2,3}0={2,4}
1
13
15
最小化DFA:
0
1
04
∴划分为{0,1,2}和{3}
∵{0,1,2}1={1,3} ∴划分为{0}和{1,2}
NFA:
I
I0
A 初 0 A,B
I1
1A
0
0,1
0,1
A 0 B 1 C0 D
A,B 1 A,B 1 A,C 2
A,C 2 A,B,D 3 A
0
A,B,D 终3 A,B,D 3 A,C,D 4
A,C,D 终4 A,B,D 3 A,D 5
2020/4/5
A,D 终5 A,B,D 3 A,D
作业评讲
5
10 10
else return (n1*n2)/n3; }
问题：没写全；表达不准确
解：< int,->,
< CInt, “CInt”> ,
< ::,-> ,
< nMulDiv, “nMulDiv”> ,
<(,->,
< int,-> ,
< n1, “n1”> , < ， , -> ,
< int,-> ,
< n2, “n2”> ,
作业评讲
44
CH.3.练习题7(P64.)
7. 问题：没构造出DFA；没过程；方法没掌握。
(1) 1(0|1)*101
解1: 正规式对应的NFA:
1
X 1 1ε 3 ε 2 1 4 0 5 1 Y
0
I
I0
I1
I
I0 I1
{X}
{1,3,2}
初0
1
{1,3,2} {3,2}
{3,4,2}
1 23
{3,2}
CH.3.练习题9(P64.)
正规式 (0|1)*010(0|1)*
DFA:
4
1
0
01
00 11 20 3
01 1
1
05
最小化DFA:
1
00
2020/4/5
0
11
1
20
0,1
3
11 11
CH.3.练习题10(P64.)
10. 用FA写出渡河的方法。
设：人---R；狼---L；羊---Y；菜---C；
< (,-> , < ==,-> , < ),-> , < 0,0> , < else,-> , < (,-> , < *,-> , < ),-> , < n3, “n3”> , <},-> 。
2020/4/5
33
CH.3.练习题5(P63.)
5. 证明3.3.1中关于正规式的交换律、结合 律等五个关系。
0 11
1
0
1
0
∵{1,2}0={2} {1,2}1={3} 最后划分得5个子集:
13 1 5
{0}, {1,2}, {3}, {4}, {5}
2020/4/5
1
作业评讲
6
CH.3.练习题7(P64.)
7. 构造下列正规式相应的DFA。 (1) 1(0|1)*101 解2: 正规式对应的NFA:
0
07
0
6 88
CH.3.练习题8(P64.)
8. 给出下面的正规表达式。
(1) 以01结尾的二进制数串; 正规式 (0|1)*01 或 (0*1*)*01
(2) 能被5整除的十进制整数; 正规式 ：
(0|1|2|3|4|5|6|7|8|9)*(0|5) 或(0*1*2*3*4*5*6*7*8*9*)*(0|5) 或(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5) (3) 英文字母组成的所有符号串, 要求符号串中的字母