【文章內容簡介】 M′，L(M)=L(M′)， 則稱 M與 M′是等價的 . 結論： ?上一個符 號 串集 V???是正規(guī)的，當且僅當存在一個 ?上的確定有窮自動機 M， 使得 V=L(M)。 DFA的確定性表現在轉換函數 f:K Σ→K 是一個單值函數，也就是說，對任何狀態(tài)k∈ K， 和輸入符號 a∈ Σ， f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉換圖來看，若字母表 Σ含有 n個輸入字符，那末任何一個狀態(tài)結點最多有 n條弧射出，而且每條弧以一個不同的輸入字符標記。 DFA的行為很容易用程序來模擬 . DFA M=（ K， Σ， f， S， Z） 的行為的模擬程序 – K:=S； – c:=getchar。 – while ceof do – {K:=f(K,c)。 – c:=getchar。 – }。 – if K is in Z then return (?yes‘) – else return (?no‘) review Regular expressions on the alphabet ? are defined by the following recursive rules: 1) Every symbol of ??is a regular expression 2) ε ?and f?is a regular expression 3) if r1 and r2 are regular expressions, so are (r1 ) r1 r2 r1 | r2 r1 * 4) Nothing else is a regular expression. ??????= {0,1,2,3,4,5,6,7,8,9} (1|2|3|4|5|6|7|8|9|0) * is a regular expression?(1|2|3|4|...8|9|0) (1|2|3...|8|9|0) * is a regular expression (1|2|3...|8|9|0)+ review DFA M=（ K， Σ， f， S， Z） 1) A finite set of states, one of which is designated the initial state or start state, and some of which are designated as final states. 2) An alphabet of possible input symbols. 3) A finite set of transitions that specifies for each state and for each symbol of the input alphabet, which state to go to next. DFA DFA ??= {digit,not digit} DFA M所能接受的符 號 串的全體記為 L(M). 對于任何兩個有窮自動機 M和 M′，L(M)=L(M′)， 則稱 M與 M′是等價的 . 結論： ?上一個符 號 串集 V???是正規(guī)的，當且僅當存在一個 ?上的確定有窮自動機 M， 使得 V=L(M)。 FA 等價 不確定的有窮自動機 NFA 定義 NFA M=?K， ?， f， S， Z?， 其中 K為狀態(tài)的有窮非空集， ? 為有窮輸入字母表， f為 K? ?* 到 K的子集（ 2 K） 的一種映射， S?K是初始狀態(tài)集， Z ?K為終止狀態(tài)集 . 例子 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} 狀態(tài)圖表示 S P Z 0 0,1 1 1 1 矩陣表示 矩陣表示 0 1S {P} {S,Z} 0P {} {Z} 0Z {P} {P} 1簡化為 0 1S P S,Z 0P . Z 0Z P P 1f為 K? ?* 到 K的子集（ 2 K） 的一種映射 具有 ?轉移的不確定的有窮自動機 – 1 2 ? ? 3 a b c 有如下定理 : 對任何一個具有 ?轉移的不確定的有窮自動機NFA N， 一定存在一個不具有 ?轉移的不確定的有窮自動機 NFA Ｍ ，使得 L(M)=L(N)。 與上例等價的一個 NFA. 2 a c b b 3 1 a c a c b b 類似 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)結到某一終態(tài)結的道路，且這條道路上所有弧的標記字依序連接成的串 (不理采那些標記為 ε的弧 )等于 t， 則稱 t可為 NFA M所識別 (讀出或接受 )。若M的某些結既是初態(tài)結又是終態(tài)結，或者存在一條從某個初態(tài)結到某個終態(tài)結的道路 ,其上所有弧的標記均為 ε，那么空字可為 M所接受。 000 111 1010001 110000001 00 01100 NFA M所能接受的符 號 串的全體記為 L(M) 結論： ?上一個符 號 串集 V???是正規(guī)的，當且僅當存在一個 ?上的不確定的有窮自動機 M， 使得 V=L(M)。 (0|1)*(000|111)(0|1) DFA是 NFA的特例 .對每個 NFA N一定存在一個 DFA Ｍ ，使得 L(M)=L(N)。 對每個NFA N存在著與之等價的 DFA M。 有一種算法，將 NFA轉換成接受同樣語言的 子集法 . 與某一 NFA等價的 DFA不唯一 . 從 NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在 DFA的矩陣表示中，表項是一個狀態(tài)， NFA到相應的 DFA的構造的基本思路是： DFA的每一個狀態(tài)對應 NFA的一組狀態(tài) . DFA使用它的狀態(tài)去記錄在 NFA讀入一個輸入符號后可能達到的所有狀態(tài) . NFA確定化算法 : 假設 NFA N=(K, ?,f,K0,Kt)按如下辦法構造一個 DFA M=(S, ?,d,S0,St)， 使得L(M)=L(N)： 1. M的狀態(tài)集 S由 K的一些子集 組成。用 [S1 S2... Sj]表示 S的元素，其中 S1, S2,... Sj是 K的狀態(tài)。并且約定，狀態(tài) S1, S2,... Sj是按某種規(guī)則排列的，即對于子集 {S1, S2}={ S2, S1,}來說， S的狀態(tài)就是 [S1 S2]； 2 M和 N的輸入字母表是相同的，即是 ?； 3 轉換函數是這樣定義的： d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = ?closure(move({S1, S