編譯原理-第6講(第四章)-資料下載頁
2025-08-05 20:28本頁面
【正文】 例等價(jià)的一個(gè)NFA 類似 DFA, 對(duì) NFA M=?K， ?， f， S， Z?也有如下定義 ∑*上的符號(hào)串 t在 NFA M上運(yùn)行： 一個(gè)輸入符號(hào)串 t，（ 我們將它表示成Tt1的形式，其中 T∈ ∑， t1∈ ∑*）在 NFA M上 運(yùn)行 的定義為： f（ Q， Tt1） =f（ f（ Q， T）， t1） 其中 Q∈ K. ∑*上的符號(hào)串 t被 NFA M接受： 若 t? ∑*， f(S0， t)=P， 其中 S0 ∈ S， P ? Z， 則稱 t為 NFA M所 接受 （ 識(shí)別 ） ∑ *上的符號(hào)串 t被 NFA M接受也可以這樣理解 對(duì)于 Σ﹡ 中的任何一個(gè)串 t， 若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為 ε的弧 )等于 t， 則稱 t可為NFA M所識(shí)別 (讀出或接受 )。 若 M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路 ,其上所有弧的標(biāo)記均為 ε，那么空字可為 M所接受。 例子 000 111 1010001 110000001 00 01100 結(jié)論 NFA M所能接受的符號(hào)串的全體記為 L(M) 結(jié)論： ?上一個(gè)符 號(hào) 串集 V???是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè) ?上的不確定的有窮自動(dòng)機(jī) M，使得 V=L(M)。 (0|1)*(000|111)(0|1)*
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1