2.4.2NFAM的确定化NFA的确定化是指对给定的NFA都能相应地构造出一个与之等价的DFA，使它们能够识别相同的语言。我们采用子集法来对NFAM确定化。首先定义FAM的一个状态子集I的ε_闭包，即ε_CLOSURE(I)，则：(1)若si∈I，则si∈ε_CLOSURE(I)；(2)若si∈I，则对从si出发经过ε通路所能到达的任何状态sj，都有sj∈ε_CLOSURE(I)。其次，对FAM的一个状态子集I，若a是Σ中的一个字符，定义Ia=ε_CLOSURE(J)第63页，共115页，星期日，2025年，2月5日其中，J是所有那些可以从I中的某一状态出发经过有向边a而能到达的状态集。?例2.7已知一状态转换图如图2–13所示，且假定I=ε_{1}={1，2}，试求从状态I出发经过一条有向边a而能到达的状态集J和ε_CLOSURE(J)。第64页，共115页，星期日，2025年，2月5日图2–13例2.7的状态转换图第65页，共115页，星期日，2025年，2月5日[解答]从状态I中的状态1或状态2出发经过一条a弧而能到达的状态集J为{5，3，4}若si∈J，则由si出发经过任意条ε有向边而能到达的任何状态sj∈ε_CLOSURE(J)，因此ε_CLOSURE(J)为{5，6，2，3，8，4，7}第66页，共115页，星期日，2025年，2月5日用子集法对NFA确定化的方法如下：(1)构造一张转换表，其第一列为状态子集I，对不同的a(a∈Σ)在表中单设一列Ia。(2)表的第一行第一列其状态子集I为ε_CLOSURE(s0)；其中，s0为初始状态。(3)根据第一列中的I为每一个a求其Ia并记入对应的Ia列中，如果此Ia不同于第一列已存在的所有状态子集I，则将其顺序列入空行中的第一列。(4)重复步骤（3）直至对每个I及a均已求得Ia，并且无新的状态子集Ia加入第一列时为止；此过程可在有限步后终止。第67页，共115页，星期日，2025年，2月5日(5)重新命名第一列的每一状态子集，则转换表便成为新的状态转换矩阵，其状态转换函数f是S×Σ到S的单值映射，即为与NFAM等价的DFAM。例2.8正规表达式（a∣b）*(aa∣bb)(a∣b)*的NFAM如图2–14所示，试将其确定化为DFAM。[解答]用子集法将图2-14所示的NFAM确定化为表2.4。对表2.4中的所有子集重新命名，得到表2.5的状态转换矩阵及对应的状态转换图(见图2-15)。第68页，共115页，星期日，2025年，2月5日图2–14例2.8的NFAM第69页，共115页，星期日，2025年，2月5日表2.4例2.8的转换表IIaIb{X,1,2}{1,2,3}{1,2,4}{1,2,3}{1,2,3,5,6,Y}{1,2,4}{1,2,4}{1,2,3}{1,2,4,5,6,Y}{1,2,3,5,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,4,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}第70页，共115页，星期日，2025年，2月5日图2–15例2.8未化简的DFAM′第71页，共115页，星期日，2025年，2月5日表2.5例2.8的状态转换矩阵Sab012132214335464564635第72页，共115页，星期日，2025年，2月5日2.4.3DFAM的化简对NFA确定化后所得到的DFA可能含有多余的状态，因此还应对其进行化简。所谓DFAM的化简，是指寻找一个状