week2-第三章-有限自動機(已改無錯字)
2022-08-21 16:18:48 本頁面
【正文】 L={x000y | x,y∈ {0,1}*} q3q0q1q20 0 00 , 10 , 1q3q0q1q20 0 01110 , 1比較： 其相應(yīng)的 DFA： 23 College of Computer Science amp。 Technology, BUPT 二 、 NFA的狀態(tài)轉(zhuǎn)移函數(shù) ?與 DFA 唯一不同之處 ? : Q ? T ? 2Q 同樣 , δ可擴展為 δ’ ( ??: Q ? T* ? 2Q) 39。(q, ε) = {q} 含義 : 不允許無輸入的狀態(tài)變化 . 39。(q,ωa)={p|存在 r∈ δ39。(q,ω)∧ p∈ δ(r,a)} ? 含義 :δ‘(q,ωa)對應(yīng)的狀態(tài)集合是 δ’(q,ω)對應(yīng)的每個狀態(tài) 下再 接收字符 a以后可能到達的狀態(tài)集合的并集 . 即 若 ?? ( q , ω) = {r 1 , r 2 , ? , r k }, 則 ?? ( q , ωa) = ? ? ( r i , a ) 其中 ω ? T* , a ? T， r i ? Q 24 College of Computer Science amp。 Technology, BUPT ? 舉例 ?? ( p , ? ) = { p } ?? ( p , 0 ) = { q } ?? ( p , 01 ) = { q , r } ?? ( p , 010 ) = { q } ?? ( p , 0100 ) = { q } ?? ( p , 01001 ) = { q , r } p q ? r 0 { q } ? { q } ? { q, r } ? 1 擴展轉(zhuǎn)移函數(shù)適合于輸入字符串 S t a r tp r0 , 10q125 College of Computer Science amp。 Technology, BUPT NFA 接受的語言 ? 設(shè)一個 NFA A = (Q, T, ?, q0 , F ) ? 定義 A 的語言： L(A) = ? ω ? ?? ( q0 , ω) ? F ? ? ? 26 College of Computer Science amp。 Technology, BUPT 第三節(jié) NFA與 DFA的等價性 ? DFA是 NFA的特例 , 所以 NFA必然能接收 DFA能接收的語言 . 因此 證明等價性只要能夠證明一個 NFA所能接收的語言必能被另一個 DFA所接收 。 : 設(shè)一個 NFA接受語言 L, 那么必然存在一個 DFA接受 L。 2. 證明 : ? 策略 :對于任意一個 NFA,構(gòu)造一個接收它所能接收語言的 DFA， 這個 DFA的狀態(tài)對應(yīng) 了 NFA的狀態(tài)集合 。 27 College of Computer Science amp。 Technology, BUPT 從 NFA 構(gòu)造等價的 DFA (子集構(gòu)造法 ) ? 設(shè) L 是某個 NFA N = (QN, T, ?N , q0 , FN) 的語言 , 則存在一個 DFA M , 滿足 L(M) = L(N) = L. ? 證明 : 定義 M = (QD, T, ?D , {q0 }, FD ) , 其中 ? QD = ? S ? S ? QN ? = 2 Q ? 對 S ? QD 和 a ? T , ?D ( S , a ) = ? ?N (q,a) . ? FD = ?S?S ? QN ? S ? FN ? ? ? 需要證明 : 對任何 ω ? T* , ??D ( {q0 } , ω ) = ??N (q0 , ω). 歸納于 | w | 可 證上述命題 . q ? S 28 College of Computer Science amp。 Technology, BUPT p q
電大資料相關(guān)推薦
鄂ICP備17016276號-1