1.假定NFA M=<S,∑,f,S0,F> 对M的状态转换图进行以下改造:
①引进新的初态结点X和终态结点Y, X,Y∈S, 从X到S0中的任意结点连一条ε箭弧，从F中任意结点到Y连一条ε箭弧。(解决初态的唯一性)
②引入新状态对M的状态转换图进行进一步的替换(简化弧上的标记)
2.NFA确定化：子集法(解决弧和转换问题)
设I是S的一个子集
①J为I中的某个状态经过一条a弧而到达的集合
②ε-closure(I)：I∪{s'|从s∈I出发经过任意条ε弧能到达s'}
③Ia=ε-closure(J)
例：
I=ε-closure({1})={1,2}
J={5,4,3}
Ia=ε-closure({5,4,3})={5,4,3,6,2,7,8}
3.状态集转换表：
设只含两个字符a,b
①置第一行第一列为ε-closure({X}),求出Ia,Ib
②检查Ia,Ib看其是否已出现在表中的第一列，把未曾出现的填入后面空行的第一列，再求出Ia,Ib
③重复上述过程，直到所有2,3列子集全部出现在第一列为止
例：
化简和确定化的状态转换图：
