编译原理 NFA转换为等价DFA 子集法 简明理解

子集法总体思路

NFA不确定的有穷自动机要转换为DFA确定的有穷自动机，就需要把“多态”的地方变为“单态”，即让DFA的每一个状态对应NFA的一组状态。

两个基本运思想

ε-closure(I)：I的ε-闭包

在DFA中，如果输入的是一个空串，状态并不会改变。

于是由该集合中各个经过任意条ε弧到达的所有状态组成的集合，在DFA中可以看为一个状态。

可以理解为，ε弧前后状态属于是同一个状态；因此I集合自己的每个状态都属于自己的ε-闭包。

move(I,a)： a弧转换

集合I中各个状态，经过一条a弧到达的状态的集合，成为集合J。

可以这么理解，前面说到总体思想是用DFA的一个状态对应NFA的一组状态。把这里的集合I看作是前面一个状态，move(I,a)即就是f(I,a)=J。

ε-closure(move(I,a))：转换到下一状态

集合I中所有状态经过一条a弧到达的状态集合加上该集合各个经过任意条ε弧到达的状态，形成了一个新的状态集合。

根据使用NFA一组状态对应DFA一个状态的总体思想，该集合即可对应DFA中状态I的下一个状态。

具体步骤 使用书上的实例

在NFA在是一个状态集，在DFA中就是一个状态。
DFA（NFA）：状态（集）。
这里使用表格分析的方式，获取到一个状态集就加入到子集族，标记一个状态集，就列入到表格中的I列，同时求得a、b弧的ε-闭包（也是一个状态集），并加入到子集族（已存在则忽略，直到子集族中所有状态集均被标记）

首先获取初态(集)T0

T0 = ε-closure（0） = {0，1，2，4，7}

标记T0：获取下一状态(集)T1、T2

因为在这个NFA中一共只有两种非终结符集，所以在DFA中T0状态最多出去两条弧，下一个状态至多有两种，这里的确有两种弧出去到达了两种状态，分别命名为T1、T2。

T1 =  ε-closure（move(T0,a)）= ε-closure(3, 8) 
= {6,1, 2, 4, 7, 3, 8} = {1,2,3,4,6,7,8}

T2 = ε-closure（move(T0,b)）= ε-closure(5)
 = {5,6,7,1,2,4} ={1,2,4,5,6,7}

标记T1：获取下一状态集T3

通过ε-closure(move(I,a))转换到下一个状态(集)，如果该状态(集)已经存在与子集族中，
就不需要重复加入，否则将该状态（集）作为未标记的状态集加入到子集族C中。

ε-closure（move(T1,a)）= ε-closure({3, 8})
 = {6,1, 2, 4, 7, 3, 8} = {1,2,3,4,6,7,8}
// 即T1，已在子集族中。

T3 = closure（move(T1,b)）= ε-closure({5,9}) = {1,2,4,5,6,7,9}

标记T2：获取下一状态集（没有新状态集）

重复从某子集C中的状态集获取下一状态集的过程并且再子集C中标记该状态集，直到子集C中不存在未被标记的集合。

closure（move(T2,a)）= ε-closure({3,8})
 = {6,1, 2, 4, 7, 3, 8} = {1,2,3,4,6,7,8}
 // 即T1，已在状态集中

closure（move(T2,b)）= ε-closure({5,9}) = {1,2,4,5,6,7,9}
// 即T2，已在状态集中

标记T3：获取下一状态集T4

closure（move(T3,a)）= ε-closure({3,8})
 = {6,1, 2, 4, 7, 3, 8} = {1,2,3,4,6,7,8}
 // 即T1，已在状态集中

T4 = closure（move(T3,b)）= ε-closure({5,10}) = {1,2,4,5,6,7,10}

标记T4：获取下一状态集（没有新状态集）

当子集C中所有的状态集合都被标记后算法结束。
标记T4算法结果，子集C全部被标记，算法结束

closure（move(T4,a)）= ε-closure({3,8})
 = {6,1, 2, 4, 7, 3, 8} = {1,2,3,4,6,7,8}
 // 即T1，已在状态集中

closure（move(T2,b)）= ε-closure({5,9}) = {1,2,4,5,6,7,9}
// 即T2，已在状态集中

根据表格得到转换函数，画出最终的DFA

根据表格，每一行，第一列经过a/b弧到达第2/3列。即为转换函数

分析结果如下，D是根据表格得到的转换函数；S是状态集合；ε是终结符集；S0是开始状态（开始符）；St是终结状态（终结符）
开始状态即最开始的状态集T0，终结状态位包含了NFA终结态10的T4

下一期：LL(1) 文法分析