編譯原理-第6講(第四章)-預(yù)覽頁(yè)
【正文】 有窮自動(dòng)機(jī) (也稱有限自動(dòng)機(jī) )作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)式所表示的集合 .應(yīng)用有窮自動(dòng)機(jī)這個(gè)理論，為詞法分析程序的自動(dòng)構(gòu)造尋找有效的方法和工具。 f（ S， baab） = f（ f（ S， b）， aab） = f（ V， aab） = f（ f（ V， a）， ab） = f（ U， ab） = f（ f（ U， a）， b） = f（ Q， b） = Q Q屬于終態(tài)。 while ceof do { K:=f(K,c)。 與上例等價(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í)別 (讀出或接受
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1