第4 章作业答案.doc

第4章 词法分析
1.构造下列正规式相应的DFA.
（１） 1(0|1)　*101
答案：
1) 先构造NFA：
1
1
1
0
0/1
A
X
B

Y
C

2)将NFA 确定化:
∑
Q
0
1
[X] X

[A] A
[A] A
[A] A
[A,B] B
[A,B] B
[A,C] C
[A,B] B
[A,C] C
[A] A
[A,B,Y] Y
[A,B,Y] Y
[A,C] C
[A,B] B
3) DFA:

2. 已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，
M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。
答案：
1) 根据题中映射，得如下NFA转换矩阵：

0
1
x
z
x
y
x,y

z
x,z
y
2) 转成NFA（这步可省）：

3) 确定化：
∑ Q
0
1
[x] X
[z] A
[x] X
[z] [A]
[x,z] B
[y] C
[x,z] [B]
[x,z] B
[x,y] E
[y] C
[x,y] E

[x,y] E
[x,y,z] F
[x] X
[x,y,z] [F]
[x,y,z] F
[x,y] E

4. 将下图的（a）和（b）分别确定化和最小化：

（a） 确定化：
∑ Q
a
b
[0] [0]
[0,1] 1
[1] 2
[0,1] [1]
[0,1] 1
[1] 2
[1] 2
[0] 0

最小化：
º0º {0,1} {2}
因为：{0,1}a={1} {0,1}b={2} 不能拆分
º1º {0,1} {2}
0,1二状态合并，得

（b） 因为自动机（b）已确定化，所以只做最小化：
º0º {1,2,3,4,5} {0}
因为 {4}a={0} {1,2,3,5}a={1,2,3, 5}
º1º {1,2,3,5} {4} {0}
因为{1,5}b={4} {2,3}b={2,3}
º2º {1, 5} {2,3} {4} {0}
因为 {2}a={1} {3}a={3}
º3º {1, 5} {2} {3} {4} {0}
因为 {1, 5}a={1,5} {1, 5}b={4} 不能拆分
º4º {1, 5} {2} {3} {4} {0}
将 {1, 5}合并得：

5.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1 都有0 直接跟在
右边。并给出该语言的正规式。
答案：
1)按题意相应的正规表达式可为(0 | 10)*， 构造相应的DFA：

2)将DFA转成右线性文法：
S-〉A|ε
A->0A|0|1B
B->0A|0

8.给出下述文法所对应的正规式：
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

10.构造下述文法G[S]的自动机：
S->A0
A->A0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？
答案：
1) 将题中左线性文法转换为自动机：
因为是左线性文法，要增加一开始状态X，开始符号S成终结状态：

2) 该自动机为NFA，确定化：
∑ Q
0
1
[x] X
[A] A

[A] A
[A,S] B

[A,S] [B]
[A,S] B
[A] A

3) 该自动机表达的语言用正规式表示为：00(0|10)*， 或：
以00开头，0结尾，中间若有1，则1后一定跟0。

附加题：
已有NFA M=（{S，A，B，F}，{0,1},f,{S},{F}）,状态图如下图所示，
1． 将此NFA转化成规范DFA；
2． 转化成正规文法。
3. 列出它拒绝接受的2个字符串（不同字符开头）

答案：
1. 确定化：
∑
Q
0
1
[S] S
[A,F] A

[A,F] [A]
[A,F] A
[A,B] B
[A,B] B
[A,F] A
[A,B,F] C
[A,B,F] [C]
[A,F] A
[A,B,F] C

此DFA已为最小化的DFA

2. 转化成右线性的正规文法
S->0A|0
A->0A|0|1B
B->0A|0|1C|1
C->0A|0|1C|1
3. 列出它拒绝接受的2个字符串（不同字符开头）
1)10000 (所有1开头的串)
2)00000(所有0结尾的串)