这里给出严谨的定理描述：
对于字母表 \Sigma 上的任一NFA M，必存在 \Sigma 上与M等价的DFA M'
证明如下：
设
NFA： M=(K,\Sigma,f,S_0,Z)
DFA： M'=(K',\Sigma,f',S_0',Z')
且该DFA为如下构造：
（1）、K'由K的全部子集组成，即 |K'|=2^K ，例如，对于K的一个子集 \{S_1,S_2,...,S_i\} ，我们用记号 [S_1,S_2,...,S_n] 表示K'中的一个状态，特别地，令 S_0'=[S_0] （开始状态）
（2）、
当且仅当
f(\{S_1,S_2,...,S_i\},a)=\{R_1,R_2,...,R_j\}
时,
f'([S_1,S_2,...,S_i],a)=[R_1,R_2,...R_j]
（3）、
Z'=\{[S_p,S_q,...,S_r]|[S_p,S_q,...,S_r]\in K'\cap\{S_p,S_q,...,S_r\}\cap Z\ne \phi\}
为了证明该定理，需证明L(M')=L(M)，为此：
设x为一输入串，且 |x|=n\ge 0 ，
为了证明L(M')=L(M)，只需证明，对于任意的输入串x，都可以使M/M'从起始状态走到终止状态
或者证明一个更强一点的论断：对于任意的输入串x，都可以使M/M'从起始状态走到相同的状态集
更准确的说法是：
当且仅当
f(S_0,x)=\{S_1,S_2,...,S_m\}
时，
f(S_0',x)=[S_1,S_2,...,S_m]
首先，我们讨论 |x|=0 的情况，显然此时， x=\epsilon
显然有 f(S_0,\epsilon)={S_0} 以及 f'(S_0',\epsilon)={S_0'} ，而我们又知道 S_0'=[S_0] ，因此后式可以变换为：
f'(S_0',\epsilon)=[S_0]
同时前式可以写为：
f(S_0,\epsilon)=\{S_0\}
因此，在此种情况下，论断成立。
紧接着，我们设 a\in \Sigma ，并假设上述论断对于x成立，且 f(S_0,x)=\{S_1,S_2,...,S_m\}
那么对于输入串xa而言，
f(S_0,xa)=f(f(S_0,x),a)=f(\{S_1,S_2,...,S_m\},a)=\{S_p,S_q,...,S_r\}
同时我们根据上述DFA构造方法中的第二步（关于映射f'的构造方法）可知：
f'(S_0',xa)=f'(f(S_0',x),a)=f'([S_1,S_2,...,S_m],a)=[S_p,S_q,...,S_r]
显然，在此种假设情况下，论断也成立。
根据数学归纳法可知，论断成立，
根据上述强论断很容易可以得出：
当前仅当 f(S_0,x) 含有Z中的状态时， f'(S_0',x)\in Z'
因此，当前仅当 x\in L(M) 时， x\in L(M')
因此原命题成立，QED。