这里首先引入可区分状态的概念：设[latex]M=(K,\Sigma,f,S_0,Z)[/latex]为以DFA，并设s和t是M的两个不同状态我们说状态s,t被某一输入串w所区分，是指从s,t中之一触发，当扫视完w之后到…

这里给出严谨的定理描述：对于字母表[latex]\Sigma[/latex]上的任一NFAM，必存在[latex]\Sigma[/latex]上与M等价的DFAM'证明如下：设NFA：[latex]M=(K,\Sigma…