編譯原理-第6講(第四章)-預(yù)覽頁
【正文】 有窮自動機 (也稱有限自動機 )作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)式所表示的集合 .應(yī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)。 與上例等價的一個NFA 類似 DFA, 對 NFA M=?K， ?， f， S， Z?也有如下定義 ∑*上的符號串 t在 NFA M上運行： 一個輸入符號串 t，（ 我們將它表示成Tt1的形式，其中 T∈ ∑， t1∈ ∑*）在 NFA M上 運行 的定義為： f（ Q， Tt1） =f（ f（ Q， T）， t1） 其中 Q∈ K. ∑*上的符號串 t被 NFA M接受： 若 t? ∑*， f(S0， t)=P， 其中 S0 ∈ S， P ? Z， 則稱 t為 NFA M所 接受 （ 識別 ） ∑ *上的符號串 t被 NFA M接受也可以這樣理解 對于 Σ﹡ 中的任何一個串 t， 若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為 ε的弧 )等于 t， 則稱 t可為NFA M所識別 (讀出或接受
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1