1 (1 ）对给定正规式b*(d|ad) (b|ab) (b|ab）* ，构造其 NFA M ；

（ 2) 对给定正规式 (a|b) *a (a|b) ，构造其 DFA M 。

【解答】（1)构造该正规式的NFA M,如下图所示。

（2）d的NFA M 其次，用子集法将其确定化。  状态转换矩阵其状态图如下图2所示。最后进行最小化化简。首先将其分为终态集(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'如图3所示。

2构造一个 DFA, 它接收∑ = ｛ a,b ｝上的所有满足下述条件的字符串，即该字符串中的每个 a 都有至少一个 b 直接跟在其右边。

 已知∑＝｛a,b｝，根据题意得出相应的正规式为：（ ab|b）*。根据此正规式画出相应的NFA M,如下图所示。

子集法：                                             重命名

I            Ia           Ib                       S         a        b

{X,1,Y}     {2}          {1,Y}                    0          1       2

{2}         /           {1,Y}                     1          /        2 

{1,Y}      {2}          {1,Y}                     2         1         2

3. 将图 2.58 所示的 DFA 最小化。 图 2.58 DFA

【解答】最简DFA如图2.65所示。

4.已知正规式 (1)((a|b) * |aa) * b 和正规式 (2)(a|b) * b 。 (1) 试用有限自动机的等价性证明正规式 (1) 和 (2) 是等价的。 (2 ）给出相应的正规文法。

【解答】 (1)正规式（1)对应的NFA如图2.36所示。用子集法将图2.36所示的NFA确定化为DFA,如图2.37所示。由于对非终态的状态1、2来说，它们输入a, b的下一状态是一样的，故状态1和状态２可以合并，将合并后的终态3命名为2，则得到表2.5（注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。由此得到最简DFA,如图2.38所示。正规式(2)对应的NFA如图2.39所示。用子集法将图2.39所示的NFA确定化为如图2.40所示的状态转换矩阵。比较图2.40与图2.37,重新命名后的转换矩阵是完全一样的，也即可以同样得到化简后的DFA如图2.38所示。所以两个自动机完全一样，即两个正规文法等价。 (2）对图2.38,令A对应状态1，B对应状态2,则相应的正规文法G[A]为： G[A]：A→aA|bB|b B→aA|bB|b G[A]可进一步化简为G[S]: S→aS|bS|b（非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合并为一个产生式）。