第4 章作业答案

第4章 词法分析

1.构造下列正规式相应的DFA.

（１） 1(0|1)　*101

答案：

1) 先构造NFA：

2)将NFA 确定化:

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转换矩阵：

2) 转成NFA（这步可省）：

3) 确定化：

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

（a） 确定化：

最小化：

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，确定化：

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. 确定化：

此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结尾的串)

本文来源：https://www.2haoxitong.net/k/doc/6d72e46a52d380eb62946d94.html