每一台NFA都有一台等价的DFA
设是识别语言A的NFA，要构造一套DFA M 识别A。再给出完整的构造之前，先考虑比较容易的情况，假设N没有
箭头。以后再吧
箭头考虑进来。
构造)
:
M的每一个状态是N的一个状态子集。是Q的所有子集组成的集合。
- 对于
和
，令
如果R是M的一个状态，则他是N的一个状态子集，所以取这些子集的并。这个表达式也可以用另一种方式写成：
- $q'_o={q_0}$$
M开始时所在的状态对应于只含N的起始状态的集合。
如果当时N的可能状态中有一个接受状态，则机器M接受。
考虑 
箭头
对于M的任意一个状态R，定义E(R)为从R出发，只沿着 箭头可以到达的状态集合，包括R本身的所有成员在内。形式地，对于
令：
然后我们修改M的转移函数，使得在每一步之后，再沿着箭头可以达到的所有状态上也放上手指。用
代替
能产生这个效果。于是：
此外还需要修改M的起始状态，使得开始时把手指移动到从N的起始状态出发，沿着箭头可以到达的所有的状态上。把
改成
能产生这个效果。
