【正文】 每個結(jié)點所射出的弧可以是Σ中一個字符或是ε . S0— 初態(tài)集 F— 終態(tài)集 δ — 轉(zhuǎn)換函數(shù) SΣ ∪ {ε } → 2S (2S S的冪集 — S的子集構(gòu)成的集合） 例 1： NFA M=({S,P,Z},{0,1},f,{s,p},{z}) 其中 f(s,0)={p} f(z,0)={p} f(p,1)={z} f(z,1)={p} f(s,1)={s,z} ① NFA的狀態(tài)圖表示如下： 第 3 頁，共 22 頁 ② NFA矩陣表示： 狀態(tài) 字符 0 1 S P S,Z 0 P {} Z 0 Z P P 1 確定有限自動機 DFA DFA(deterministic finitestate automata)即確定有限自動機，一個確定的有限自動機 DFA M 是一個五元式 : M=(S, Σ，δ , S0, Z) 其中 : S — 有限狀態(tài)集 Σ — 輸入字母表 δ — 映射函數(shù) (也稱狀態(tài)轉(zhuǎn)換函數(shù) ) SΣ→ S S P Z 1 0,1 1 0 1 第 4 頁，共 22 頁 δ (s,a)=S’ , S, S’ ∈ S, a∈Σ S0 — 初始狀態(tài) S0 ∈ S Z— 終止狀態(tài)集 Z?S 例 2： DFA M=({S,U,V,Q},{a,b},f,s,{Q}) 其中 f的定義為： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q ① DFA 的狀態(tài)圖表示： 假如 DFA M 含有 m 個狀態(tài)， n個輸入符，那么這個狀態(tài)含有 m個節(jié)點，每個節(jié)點最多有 n 個弧射出，整個圖整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“ =”或標以“ ”，終態(tài)結(jié)點用雙圈表示或標以“ +”，若 f(ki ,a)=kj，則從狀態(tài)結(jié)點 ki 到狀結(jié)點 kj畫標記為 a 的?。? ② DFA 矩陣表示： 一個 DFA 還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即 k行 a列為 f(k,a)的值。 （ 2）掌握 NFA 確定化的過程。 deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA 目錄 ： ............................................................ 1 背景 ......................................................... 1 實踐目的 ..................................................... 1 課程實踐的意義 ............................................... 1 和 DFA 的概念 .................................................. 2 不確定有限自動機 NFA......................................... 2 確定有限自動機 DFA ........................................... 3 3．從 NDF 到 DFA的等價變化步驟 ...................................... 5 轉(zhuǎn)換思路 ..................................................... 5 .................................................. 5 子集構(gòu)造法 ................................................... 7 4程序?qū)崿F(xiàn) .......................................................... 9 程序框架圖 ................................................... 9 數(shù)據(jù)流程圖 .................................................. 9 實現(xiàn)代碼 .................................................... 10 運行環(huán)境 .................................................... 10 程序?qū)崿F(xiàn)結(jié)果 ................................................ 10 ......................................................... 12 ： ....................................................... 12 考 文 獻 ..................................................... 12 8. 附錄 ............................................................ 13 第 1 頁，共 22 頁 ： 背景 有限自動機作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。本文主要是介紹如何將 NFA轉(zhuǎn)換為與之等價的簡化的 DFA，通過具體實例，結(jié)合圖形，詳細說明轉(zhuǎn)換的算法原理。而 DFA 則是確定的 ,將 NFA轉(zhuǎn)化為 DFA將大大提高工作效率 ,因此將 NFA轉(zhuǎn)化為 DFA是有其一定必要的。 在非確定的有限自動機 NFA 中 ,由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個 NFA 對符號串的識別就必然是一個試探的過程。 編譯原理課程實踐報告 設(shè)計名稱： N