week2-第三章-有限自動(dòng)機(jī)(參考版)
2024-08-04 16:18本頁(yè)面
【正文】 Technology, BUPT 構(gòu)造識(shí)別下述語(yǔ)言的確定性有限自動(dòng)機(jī) { x | x∈ {0,1}+ 并且 x 含形如 10110的子串 } { x | x∈ {0,1}+ 并且 x 以 0開頭，以 1結(jié)尾 } * { x | x∈ {0,1}+ 并且 x 串代表的二進(jìn)制數(shù)能整除 3} { x | x∈ {0,1}+ 并且 如果 x以 1開頭則長(zhǎng)度為偶數(shù)，如果 x以 0開頭，則長(zhǎng)度為奇數(shù) } P120 習(xí)題 10, 14 作業(yè)： 。 Technology, BUPT 證明 :從 NFA 構(gòu)造等價(jià)的 DFA ? 設(shè) N = (QN, T, ?N , q0 , FN) 是一個(gè) NFA , 通過(guò)子集構(gòu)造法 得到相應(yīng)的 DFA D = (QD, T, ?D , [q0 ], FD ), 則 對(duì)任何 ω ? T* , ??D ( {q0 } , ω ) = ??N (q0 , ω). ? 證明 :歸納于 | ω | 1 設(shè) | ω | = 0, 即 ω = ? . 由定義知 ??D ( {q0 }, ? ) = ??N (q0 , ?) = {q0 }. 2 設(shè) | ω | = n+1, 并 ω = xa, a ? T . 注意到 | x | = n. 假設(shè) ??D ( {q0 } , x ) = ??N (q0 , x) = { p1 , p2 , ? , pk }. 則 ??D ( {q0 } , ω ) = ?D (??D ( { q0 } , x ) , a ) = ?D ( { p1 , p2 , ? , pk }, a ) = ? ?N (pi , a). = ??N (q0 , ω) i = 1 k 31 College of Computer Science amp。 Technology, BUPT p q ? r 0 { q } ? { q } ? { q, r } ? 1 0 ? { q } 1 ? { p } { q } ? { r } { p, q } ?{ p, r } ?{ q, r } ?{ p, q, r } ? ? { q } { q, r } ? ? { q } { q, r } { q } ? { q } { q, r } { q } { q, r } S t a r t{ p }0 , 10{ q }1{ q, r }1010? 子集構(gòu)造法舉例 初始的 NFA 子集構(gòu)造，計(jì)算狀態(tài)可達(dá) 經(jīng)篩選后的 DFA 29 College of Computer Science amp。 27 College of Computer Science amp。 : 設(shè)一個(gè) NFA接受語(yǔ)言 L, 那么必然存在一個(gè) DFA接受 L。 Technology, BUPT NFA 接受的語(yǔ)言 ? 設(shè)一個(gè) NFA A = (Q, T, ?, q0 , F ) ? 定義 A 的語(yǔ)言： L(A) = ? ω ? ?? ( q0 , ω) ? F ? ? ? 26 College of Computer Science amp。(q,ω)∧ p∈ δ(r,a)} ? 含義 :δ‘(q,ωa)對(duì)應(yīng)的狀態(tài)集合是 δ’(q,ω)對(duì)應(yīng)的每個(gè)狀態(tài) 下再 接收字符 a以后可能到達(dá)的狀態(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。(q, ε) = {q} 含義 : 不允許無(wú)輸入的狀態(tài)變化 . 39。 Technology, BUPT ? 例：構(gòu)造 NFA，可識(shí)別 {0,1}上的語(yǔ)言 L={x000y | x,y∈ {0,1}*} q3q0q1
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1