nfa的要素中不包含哪個(gè)成分？nfa確定化和最小化講解

現(xiàn)在大家都會(huì)在網(wǎng)絡(luò)上汲取相關(guān)知識(shí)內(nèi)容，比如nfa的要素_nfa的要素中不包含哪個(gè)成分，為了更好的解答大家的問(wèn)題，小編也是翻閱整理了相應(yīng)內(nèi)容，下面就一起來(lái)看一下吧!

nfa的要素中不包含哪個(gè)成分?

初始狀態(tài)集合不是NFA的成分。

nfa確定化和最小化講解：

把 NFA 確定化為 DFA 的算法實(shí)現(xiàn)

1)轉(zhuǎn)換思路

由非確定的有限自動(dòng)機(jī)出發(fā)構(gòu)造與之等價(jià)的確定的有限自動(dòng)機(jī)的辦法是確定的有限自動(dòng)機(jī)的狀態(tài)對(duì)應(yīng)于非確定的有限自動(dòng)機(jī)的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能到達(dá)的所有狀態(tài)，也就是說(shuō)，在讀入符號(hào)串a(chǎn)1a2a3…an之后,該DFA處在這樣一個(gè)狀態(tài),該狀態(tài)表示這個(gè)NFA的狀態(tài)的一個(gè)子集T,而T是從NFA的開(kāi)始狀態(tài)沿著某個(gè)標(biāo)記為a1a2a3…an的路徑可以到達(dá)的那些狀態(tài)。

2)消除空轉(zhuǎn)移

消除N—>ε形式的產(chǎn)生式,即消除空轉(zhuǎn)移。狀態(tài)集合I的a弧轉(zhuǎn)換Ia:定義為一狀態(tài)集,是指從狀態(tài)集I出發(fā)先經(jīng)過(guò)a弧后再經(jīng)過(guò)若干條ε弧而能到達(dá)的狀態(tài)的集合。可以寫(xiě)作:Ia= ε-closure(J),J=move(I,a),其中,J是從I中任一狀態(tài)出發(fā)經(jīng)過(guò)一條a弧到達(dá)的狀態(tài)集合記為move(I,a)。

s 表示NFA的狀態(tài),T 表示NFA的狀態(tài)集合,a表示一個(gè)input symbol

ε-transition(ε轉(zhuǎn)換)就是說(shuō)input symbol為ε時(shí)的transition(轉(zhuǎn)換)

3)數(shù)據(jù)流程圖

以上就是全部?jī)?nèi)容，更多精彩請(qǐng)繼續(xù)關(guān)注小編。