构造下列正规式所对应的确定有限自动机（需要化简)： （1)（aa|b)*（a|bb)* （2)（0|1)*1 （3)（aa|bb)* （4)（＋|－
构造下列正规式所对应的确定有限自动机(需要化简)：
(1)(aa|b)*(a|bb)*
(2)(0|1)*1
(3)(aa|bb)*
(4)(-|ε)aa*
(5)(a*b)*ba(a|b)(a|b)*
(6)ab*c*d
(7)((a|b)*|bb)*
-
本题考察从正规式构造非确定有限自动机，再对非确定有限自动机用子集法进行确定化，最后最小化的方法。对本题的解答，只需按照前面介绍的方法，一步一步地进行即可。
表3-4 对(aa|b)*(a|bb)*的非确定有限自动机进行确定化
(1)首先从该正规式出发，下面用子集法进行确定化，如表3—4所示。
状态子集ab初态集{X}的ε闭包：
{X,1,0,2,Y}Next({X,1,0,2,Y},a)：
{3,2,Y}Next({X,1,0,2,Y},b)：
{1,4,0,2,Y}{3,2,Y}Next({3,2,Y},a)：
{1,2,0,Y}Next({3,2,Y},b)：
{4}{1,4,0,2,Y}Next({1,4,0,2,Y},a)：
{3,2,Y}Next({1,4,0,2,Y},b)：
{1,2,4,0,Y}{1,2,0,Y}Next({1,0,2,Y},a)：
{3,2,Y}Next({1,0,2,Y},b)：
{1,4,0,2,Y}{4}Next({4},a)：Next({4},b)：
{2,Y}{2,Y}Next({2,Y},a)：
{2,Y}Next({2,Y},b)：
{4}
表3-5 得到的(aa|b)*(a|bb)*状态转换矩阵
将状态子集重新命名，得到如表3—5所示的状态转换矩阵：
状态ab0(初态，终态)121(终态)342(终态)123(终态)124－55(终态)54
表3-6 用子集法对(0|1)*1正规式进行分解
左上角{x}的ε闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。这样，就得到确定有限自动机。 首先，状态集划分为终态集{0,1,2,3,5}和非终态集{4}。其中第二个集合已经无法进一步划分。下面考察第一个集合，看是否需要划分为不同的集合。我们看到，在该集合中，状态1和5在输入b的情况下，后继状态为4，而0，2，3在相同输入的情况下，后继状态都为2，这两组状态在相同输入的情况下，后继状态分别属于当前划分的不同子集，说明它们是可以区分的，应该将{0，1，2，3，5，6}划分为两个子集：{0，2，3)和{1，5}，这样，得到状态集合的新划分：{4}，{0，2，3}，{1，5}
下面考察，{0,2,3}和{1,5}是否可以进一步划分。考察{0,2,3}：在输入b的情况下，它们的后继状态都是2号状态，无法确定它们是可区分的；在输入a的情况下，0的后继状态是1，2和3的后继状态是1，说明1与2和3是等价的，因此删除2个状态。同样考察{1，5}：在输入b的情况下，它们的后继状态是4号状态，无法确定它们是可区分的；在输入a的情况下，1的后继状态是3，5的后继状态是5，而状态3同状态5不属于同一个集合，因此1与5是可区分的，将1和5分开，于是得到下面的划分：{4)，{0，2，3}，{1}，{5}。
经过考察，发现其中的每个状态子集都不可能进一步划分了，这样就得到了最后的划分。对每个状态子集，选一个状态作为代表，删除其余状态，把导向被删除状态的边改成导向所选择的代表状态，得到化简的确定有限自动机。
(2)同样，首先从正规式出发，构造非确定有限自动机，通过引入新的节点和边，对正规式进行分解，直至每条边或者由字母表上的字母标记，或者为空字ε。
下面用子集法进行确定化，如表3-6所示。
状态子集01初态集{X}的￡闭包：{X,1,2}Next({X,1,2},0)：
{1,2}Next({X,1,2},1)：
{1,2,Y}{1,2}Next({1,2},0)：
{1,2}Next({1,2},1)：
{1,2,Y}{1,2,Y}Next({1,2,Y},0)：
{1,2}Next({1,2,Y},1)：
{1,2,Y}
表3—7 得到的(0|1)*1状态转换矩阵
下面对状态子集重新命名，得到确定有限自动机的状态转换矩阵，如表3—7所示。
状态010(初态)121122(终态)12
表3-8 用子集法对(aa|bb)*非确定有限自动机进行确定化
下面对该确定有限自动机进行化简：
首先，把状态集合划分为终态集和非终态集：{2}和{0,1}，属于不同子集的状态之间是可以区分的。下面我们考察子集{0,1}是否可以进一步划分。首先，在输入0的情况下，0号状态停止于1号状态，1号状态也停止于1号状态，从输入符号0无法进一步区分0号状态和1号状态；在输入符号1的情况下，0号状态的后继状态是2号状态，1号状态的后继状态也是2号状态，根据输入符号1也无法区分0号状态和1号状态。因此，子集{O，1}无法进一步划分，意味着0号状态和1号状态是等价的，因此，可以删除其中之一，得到化简的确定有限自动机。
(3)构造非确定有限自动机，下面用子集法进行确定化，如表3—8所示。
状态子集ab初态集{X}的ε闭包：{X,1,Y}Next({X,1,Y},a)：
{3}Next({X,1,Y},b)：
{2}{3}Next({3},a)：
{1,Y}Next({3},b)：
Ф{2}Next({2},a)：
ФNext({2},b)：
{1,Y}{1,Y}Next({1,Y},a)：
{3}Next({1,Y},b)：
{2}
表3-9 得到的(aa|bb)*|状态转换矩阵
对状态子集重新命名，得到如表3—9所示的确定有限自动机的状态转换矩阵：
状态ab0(初态，终态)1213-2-33(终态)12
表3-10 对(+|-|ε)aa*非确定有限自动机进行确定化
下面对该确定有限自动机进行化简：
首先划分成终态集和非终态集：{0,3}，{1,2}。下面考察其中的每个状态子集，看能否进一步地划分。首先考察{0,3}，在输入a的情况下，0号状态的后继状态为1，3号状态的后继状态也为1，无法区分它们；在输入b的情况下，0和3号状态的后继状态都为2号状态，也无法区分它们，0号和3号状态是等价的，可以去掉一个。下面考察{1，2}，由于在1号状态下接受输入符号a，而在2号状态下不能接受a，因此，这两个状态是可以区分的。这样得到的最后划分为{1}，{2}，{0，3}。 其中，0号状态既是初态又是终态。
(4) 下面用子集法对这个非确定有限自动机进行确定化，如表3-10所示。
状态子集+-A初态集{X}的ε闭包：
{X,1}Next({X,1},+)：
{1}Next({X,1},-)：
{1}Next({X,1},a)：
{2,3,Y}{1}Next({1},+)：
ФNext({1},-)：
ФNext({1},a)：
{2,3,Y}{2,3,Y}Next({2,3,Y},+)：
ФNext({2,3,Y},-)：
ФNext({2,3,Y},a)：
{3,Y}{3,Y}Next({3,Y},+)：
ФNext({3,Y},-)：
ФNext({3,Y},a)：
{3,Y}
表3—11 得到的(+|-|ε)aa*状态转换矩阵
对状态子集重新命名，得到如下的确定有限自动机的状态转换矩阵如表3-11所示。
状态+-a0(初态)1121--22(终态)--33(终态)--3
表3-12 对(a*b)*ha(a|b)(a|b)*非确定有限自动机进行确定化
下面对该确定有限自动机进行化简：
首先把状态集划分成终态集和非终态集{0,1}，{2,3}，下面考察每个状态子集，看能否进一步划分。首先考察{0,1}，由于0号状态下可以接受“+”和“-”，而1号状态下不能，因此，0号状态和1号状态是可区分的，应该将该子集划分开，得到新的划分：{0}，{1}，{2，3}。在当前划分下考察，看{2，3}能否进一步划分。由于2和3号状态都只能接受输入符号a，而且在此输入下，都停止于3号状态，因此，2和3号状态是等价的，划分{0}，{1}，{2，3}就是最后划分。根据该划分，2号状态和3号状态中可以只保留一个作为代表，删除其他状态。这样得到正规式(+|-|ε)aa*的化简后的确定有限自动机。
(5)首先构造正规式(a*b)*ba(a|b)(a|b)*的非确定有限自动机，下面用子集法进行确定化，如表3-12所示。
状态子集aB初态集{X}的ε闭包：
{X,1,5,7,8}Next({X,1,5,7,8},a)：
{7,8}Next({X,1,5,7,8},b)：
{1,2,5}{7,8}Next({7,8},a)：
{7,8}Next({7,8},b)：
{1,5}{1,2,5}Next({1,2,5},a)：
{3}Next({1,2,5},b)：
{2}{3}Next({3},a)：
{4,6,Y}Next({3},b)：
{4,6,Y}{2}Next({2},a)：
{3}Next({2},b)：
Ф{4,6,Y}Next({4,6,Y},a)：
{6,Y}Next({4,6,Y},b)：
{6,Y}{6,Y}Next({6,Y},a)：
{6,Y}Next({6,Y},b)：
{6,Y}{1,5}Next({1,5},a)：
ФNext({1,5},b)：
{2}
表3-13 得到的(a*b)*ba(a|b)(a|b)*状态转换矩阵
对状态子集重新命名，得到确定有限自动机的状态转换矩阵，如表3-13所示。
状态ab0(初态)1211723435543-5(终态)666(终态)667-4
表3-14 对ab*c*d非确定有限自动机进行确定化
下面对该确定有限自动机进行化简。将状态集划分为终态集和非终态集：{5,6}，{0,1,2,3,4,7}。首先考察{5,6}，由于在输入a和b的情况下，5和6的后继状态是6号状态，该状态子集不能进一步划分。下面来考察{0，1，2，3，4，7}，由于3号状态在输入a的情况下后继状态5属于{5，6}，而{0，1，2，4}在输入a的情况下后继状态分别为1，3，属于当前划分中另一个状态子集，而7号状态不能接受输入符号a，因此{0，1，2，3，4，7}划分为{0，1，2，4}，{7}和{3}，得到当前划分：{5，6}，{0，1，2，4}，{7}和{3}。下面考察{0，1，2，4}：在输入a的情况下，0和1的后继状态为1，2和4的后继状态为3，分别属于当前划分中的不同状态子集，因此0，1与2，4是可以区分的，应该将{0，1，2，4}分裂为{0，1}和{2，4}，得到当前划分：{5，6}，{0，1}，{2，4}，{7}和{3}。现在考察{0，1}，在输入a下，它们的后继状态都是1，无法确定它们是可以区分的；在输入b下，0和1的后继状态分别为2和7，分别属于当前划分中的不同状态子集，因此0和1也是可以区分的，应该将{0，1}分裂为{O}和{1}，得到当前划分：{5，6}，{0}，{1}，{2，4}，{7}和{3}。考察{2，4}，在输入a下无法区分它们，因为它们的后继状态都是3，但是考察输入b，2号状态的后继状态是4，而4号状态不能接受输入符号b，因此2和4也是可以区分的。这样，得到最后的划分：{5，6}，{0}，{1}，{2}，{4}，{7}和{3}。据此构造正规式(a*b)*ba(a|b)(a|b)*的化简后的确定有限自动机。
(6) 下面用子集法进行确定化，如表3-14所示。
状态子集abCd初态集{X}的ε
闭包：{X)Next({X},a)：
{1,4,2,5,3}Next({X},b)：
ФNext({X},c)：
ФNext({X},d)：
Ф{1,4,2,5,3}Next({1,4,2,5,3},
a)：
ФNext({1,4,2,5,3},
b)：
{4,2,5,3}Next({1,4,2,5,3},
c)：
{5,3}Next({1,4,2,5,3},
d)：
{Y}{4,2,5,3}Next({4,2,5,3},
a)：
ФNext({4,2,5,3},
b)：
{4,2,5,3}Next({4,2,5,3},
c)：
{5,3}Next({4,2,5,3},
d)：
{Y}{5,3}Next({5,3},a)：
ФNext({5,3},b)：
ФNext({5,3},c)：
{5,3}Next({5,3},d)：
{Y}{Y}Next({Y},a)：
ФNext({Y},b)：
ФNext({Y},c)：
ФNext({Y},d)：
Ф
表3—15 得到的ab*c*d状态转换矩阵
将状态子集重新命名，得到下面的状态转换矩阵如表3-15所示。
状态abcd0初态1---1-2342-2343--344终态----
表3-16 对((a|b)*|bb)*非确定有限自动机进行确定化
左上角{X)的ε闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。这样，就得到正规式ab*c*d的未化简的确定有限自动机。下面对确定有限自动机进行最小化：
首先，状态集划分为非终态集{0,1,2,3}和终态集{4}。其中第2个集合无法进一步划分。下面考察第1个集合{0,1,2,3}，看是否需要划分为不同的集合。在该集合中，状态0只能接受a，应该将{0,1,2,3}划分为两个子集：{0}和{1,2,3}，得到状态集合的新划分：{4}，{0}，{1,2,3}
下面考察{1,2,3}是否可以进一步划分。状态1，2可以接受字符b，c，d，状态3能接受c，d，所以应该将{1,2,3}分解为{1,2}和{3}。于是得到新的划分：{0}，{1,2}，{3}，{4}
经过考察，发现其中的每个状态子集都不可能进一步划分了，得到了最后的划分。对每个状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到正规式ab*c*d的的化简后的确定有限自动机。
(7)首先从该正规式出发，构造等价的非确定有限自动机，得到了非确定有限自动机后，下面用子集法进行确定化，如表3—16所示。
状态子集ab初态集{X}的ε闭包：{X,1,3,Y}Next({X,1,3,Y},a)：
{3,1,Y}Next({X,1,3,Y},b)：
{2,3,1,Y}{3,1,Y}Next({3,1,Y},a)：
{3,1,Y}Next({3,1,Y},b)：
{2,3,1,Y}{2,3,1,Y}Next({2,3,1,Y},a)：
{3,1,Y}Next({2,3,1,Y},b)：
{2,3,1,Y}
表3—17 得到的((a|b)*|bb)*状态转换矩阵
将状态子集重新命名，得到下面的状态转换矩阵，如表3—17所示。
状态ab0初态终态121终态122终态12
左上角{x}的ε闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。得到正规式((a|b)*|bb)*的未化简的确定有限自动机。
下面对确定有限自动机进行最小化：
首先，状态集划分为非终态集Ф和终态集{0,1,2}。
考察集合{0,1,2}，发现其中的每个状态子集都不可能进一步划分，得到最后的划分：{0,1,2}。对该状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到正规式((a|b)*|bb)*的化简后的确定有限自动机。