一個(gè)非確定自動(dòng)機(jī)( NFA) 在讀入符號(hào)串之后，并不確切地知道自動(dòng)機(jī)處于哪個(gè)狀態(tài)。但可以肯定一定處于狀態(tài)集中的某一狀態(tài)。該狀態(tài)集記做 {q1,q2,…qk} 。而一個(gè)等價(jià)的確定自動(dòng)機(jī)( DFA) 讀入同樣的 w 一定處于某個(gè)確定的狀態(tài)上。這樣，都是讀入同樣的 w ， DFA 到達(dá)某一個(gè)狀態(tài)，而 NFA 到達(dá)某一個(gè)狀態(tài)集。由 w 的任意性，可將 NFA 的所有的狀態(tài)集和 DFA 的狀態(tài)一一對(duì)應(yīng)起來(lái)。這種對(duì)應(yīng)的前提就是能識(shí)別同樣的輸入串。即 L(M1)=L(M2) 。
顯然，后一個(gè)狀態(tài)集是依賴(lài)于前一個(gè)狀態(tài)集的，是在前一個(gè)狀態(tài)集的基礎(chǔ)上，（其內(nèi)任意結(jié)點(diǎn)）經(jīng)過(guò)同一條路徑到達(dá)的。下面是一個(gè)簡(jiǎn)單的例子：
可以看出，其核心是將 NFA 狀態(tài)集歸并為 DFA 中的狀態(tài)。在 NFA 中，無(wú)論是從 1 到 4 ，還是 1 到 5 ，作為集合來(lái)講都是集合 1 到集合 2 ，最為重要得是經(jīng)過(guò)的條件都是 a 。因而從識(shí)別語(yǔ)言的效果是一樣的。這使得這些弧合并成為可能。
考慮集合覆蓋的情況。
一個(gè)結(jié)點(diǎn)屬于第一個(gè)集合又同時(shí)屬于第二個(gè)集合。這種情況不一定好理解。但如果從路徑的歷史的角度進(jìn)一步區(qū)分，即不同的時(shí)間經(jīng)過(guò)同一個(gè)結(jié)點(diǎn)，將其看成是不同的狀態(tài)。按照這種時(shí)空的角度進(jìn)一步區(qū)分，得到右圖。這和圖 1 是類(lèi)似的。
再來(lái)看看帶有終態(tài)結(jié)點(diǎn)的情況：
ab ， abb 均為該 NFA 識(shí)別的句子，其轉(zhuǎn)換如下：
| | I a | Ib |
| A{1,2} | {3} | Φ |
| B{3} | Φ | {3,4} |
| C{3,4} | Φ | {3,4} |
從某種意義上說(shuō)。 NFA 中的狀態(tài) 3 在 DFA 中被分離成兩部分，當(dāng)首次到達(dá) 3 時(shí)應(yīng)該是狀態(tài) B ，而第二次以后再到達(dá) 3 則應(yīng)該屬于狀態(tài) C 。
根據(jù)規(guī)則， C{3,4} 為 DFA 的終態(tài)，但在 NFA 中，只有 4 為終態(tài)， C 中仍然有 3 為非終態(tài)，若有路徑 1 à 3 à 3 映射到 DFA 中也是 A à B à C ，何解？
這里面最關(guān)鍵的是：對(duì)任意一個(gè)句子，總可以在兩個(gè)圖中分別找到一條路徑，形成對(duì)應(yīng)關(guān)系。并不是說(shuō) NFA 中的每條路徑都要和 DFA 中的每條路徑一一對(duì)應(yīng)。
當(dāng)識(shí)別句子 ab 時(shí)，選擇由 3 直接到達(dá) 4 的路徑。當(dāng)識(shí)別句子 abb 時(shí)，則在狀態(tài) 3 循環(huán)一次再到達(dá) 4 。
現(xiàn)在設(shè)想，通過(guò) 1 à 3 à 3 經(jīng)過(guò)的路徑也是 ab 。但此時(shí)并未到達(dá)終態(tài)。可以說(shuō)，在到達(dá) C 中的 3 時(shí)，必然選擇了兩個(gè) b 以上的句子。
而這樣的路徑與選擇句子有關(guān)系。
對(duì)于 NFA 能識(shí)別的句子，在 DFA 中也能識(shí)別。
對(duì)于 NFA 不能識(shí)別的句子，在 DFA 中也不能識(shí)別。