词法分析习题 - 图文

1、画出能识别实数的状态转换图

【解答】由题可知，实数表示是建立在整数基础之上的，所以首先画出整数的状态转换图，如图2.7所示。

图2.7 整数的状态转换图

考虑到“+”、“-”符号，可画出实数的状态转换图，如图2.8所示。

图示2.8 实数的状态转换图

2、请构造与图2.9等价的最小化DFA。

【解答】

用子集法构造状态转换距阵，如表2.1所示。

将转换矩阵中的所有子集重新命名而形成表2.2所示的状态转换矩阵。

即得到M’=（｛0,1,2｝，｛a,b｝，f,0，｛1,2｝），其状态转换图如图2.10所示。

图2.10 DFA M`

将图2.10的DFA M'最小化。首先，将M'的状态分成终态组｛1，2)与非终态组｛0}; 其次，考察{ 1,2｝。由于｛1,2｝a= { 1,2｝b=｛2｝C｛1,2｝，所以不再将其划分了，也即整个 划分只有两组{0｝，{1,2}；令状态1代表{ 1,2},即把原来到达2的弧都导向1，并删除状 态2。最后，得到如图2.11所示化简了的DFA M'。

3、请构造与图2.13等价的最小化DFA。 【解答】

图2.13 （2）d的NFA M

首先，用子集法将其确定化。

图2.14 状态转换矩阵

其状态图如图2.15所示。

然后，进行最小化化简。首先将其分为终态集(3,4｝和非终态集{0,1,2｝，由于｛0} a=｛0｝b=｛2｝a｛2｝bC｛0,1,2｝，但｛1｝a=｛1｝bC｛3,4｝，故将其划分为｛0,2｝，｛1｝。对｛3｝、｛4｝也是如此，即最后划分为：{0,2｝、｛1｝、{3｝、{4｝，按顺序重新命名为1、2、3、４，则化简后的DFA M'如图2.16所示。

4、请构造与图2.17等价的最小化DFA。

用子集法将其确定化为图2.18所示。

由此得到状态图如图2.19所示。

用最小化方法化简得：｛0｝、｛1｝、｛2｝、｛３，４｝，按顺序重新命名得最终化简的DFA M', 如图2.20所示。

5、请构造与图2.24等价的最小化DFA。

用子集法将图2.24所示的NFA确定化为如图2.25所示的状态转换矩阵。

进行最小化，由于无非终态集，即划分为终态集{ 1,2,3 }，这已是最简状态，即最简的DFA, 如图2.26所示。

6、请构造与图2.27等价的最小化DFA。 【解答】

用子集法将图2.27确定化，如图2.28所示。

由图2.28重新命名后的状态转换矩阵可化简为（也可由最小化方法得到）： {0,2｝｛1｝{3,5｝{4,6} {7｝

按顺序重新命名为0, 1、2, 3, 4后得到最简的DFA,如图2.29所示。

7、请构造能识别以下语言的最小化DFA：以b打头、以aa结尾的任意由a和b组成的符号串。

【解答】根据题意，以b开头，且以aa结尾的正规式为： b(a|b) *aa 根据正规式画出NFA,如图2.30所示。

将图2.30所示的NFA确定化，如图2.31所示。

从图2.31可知己为最简状态，由于开始状态。只能输入字符b而不能与状态1合并，而状态2和状态3面对输入符号的下一状态相同，但两者一为非终态、一为终态，故也不能合并，故图2.31所示的状态转换矩阵已是最简的DFA,如图2.32所示。

8、请构造能识别以下语言的最小化DFA：至少有两个1，且任意两个1之间必须有偶数个0的任意由0和1组成的符号串。 【解答】

至少有两个1，且任意两个1之间必须有偶数个0；也即在第1个1之前和最后一个1之后，对0的个数没有要求；据此我们求出的正规式为：

0*1(00(00）*1）*00(00）*10*

画出与正规式对应的NFA,如图2.33所示。

用子集法将图2.33的NFA确定化，如图2.34所示。

由图2.34可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为：

{0}、{1｝、{2,4}、{3}、{s}、{6,8}、{7)

按顺序重新命名为0, 1, 2, 3, 4, 5, 6，则得到最简DFA一如图2.36所示。

9、请构造与图2.41等价的最小化DFA。 【解答】

首先，用子集法将NFA确定化，如图2.42所示。

由状态转换矩阵得到DFA如图2.43所示．

由状态转换矩阵可以看出：{4}和{5}面对输入字符的下一状态都是相同的，但{4}属于非终态，而{5}属于终态，故图2.43的DFA已是最简的DFA。

10、请构造与图2.44等价的最小化DFA。 【解答】

用子集法将图2.44的NFA确定化，如图2.45所示。

由状态转换矩阵得到DFA.如图2.46所示。 由状态转换矩阵可以看出：状态5和状态6面对输入符号的下一状态态都是相同的，但状态5为非终态，而状态6为终态，故图2.46的DFA已是最简的DFA。

本文来源：https://www.bwwdw.com/article/9oe5.html