NFA确定化
定理：对于一个给定的非确定的有限自动机，一定存在一个确定的有限自动机，是这两个有限自动机所识别的语言相同。
因此，我们可以由非确定的有限自动机构造与其等价的确定的有限自动机，也称为有限自动机的确定化。
构造的方法为：
用确定的有限自动机的一个状态对应不确定的有限自动机的多个状态。这种方法称为子集构造法。
在我们学习这种构造法之前，首先要了解两个定义。
1.ε-闭包
设非确定的有限自动机M=(∑，S,S0,Z,f),假设I为M的状态集S的一个子集，则定义：
ε-closure(I):
a.若q∈I, 则q∈ ε-closure(I)；
b.若q∈I，则对任意q’∈f(q,ε),有q’∈ε-closure(I)；
2.集合Ia的闭包
设非确定的有限自动机M=(Q,∑,f,q0,Z)，假定I属于Q，a∈∑，则定义Ia=ε-closure({p∈f(q,a)|q∈ε-closure(I)})，
通俗的讲，就是从I的ε-闭包出发，经过一条a弧而到达的状态集的闭包。
非确定的有限自动机的确定化算法——子集法。
1.若p为NFA初态，则DFA的初态A为ε-closure({p})。
2.若q为已生成的状态，对NFA的每一个弧进行标记，那么求ε-closure(f(q,m))。如果所求集合不为空，那么继续重复这一过程，直到不在出现新的集合。
DFA最小化
说在前面：
1.无关状态
如果从DFA的初态开始，识别任何输入序列都不能到达的那些状态称为无关状态。
2.最小的确定的有限自动机
如果确定的有限自动机既没有多余的状态，又没有互相等价的状态，即称为确定的有限自动机为最小的。
3.等价状态
设DFA的两个不同状态，如果对于任何输入序列从这两个状态出发，总是同时到达接受状态或拒绝状态，则称这两个状态为等价的。
确定的的有限自动机的最小化步骤：
1.消除无关状态
主要包含两种情况，第一种从该自动机的开始状态出发，输入任何输入串都不能到达的那个状态；
第二种是从某个状态出发都不能到达终结状态的道路。
2.消除等价状态
消除等价状态采用划分法。就是将已经去掉无关状态的DFA的状态分为一些不相关的子集。
一般第一步将终结状态与非终结状态进行基本划分，
接下来根据状态转换矩阵进行划分，对于两个状态来说，分别分析对于不同输入，如果他们到达的状态分属不同的子集中(上一步划分的集合)，那么就可以将它们分在不同的子集中，
对已划分的子集重复上述过程，最终所有子集中的状态全部等价，即可。