week2-第三章-有限自動機(jī)(更新版)
【正文】 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 NFA 接受的語言 ? 設(shè)一個 NFA A = (Q, T, ?, q0 , F ) ? 定義 A 的語言： L(A) = ? ω ? ?? ( q0 , ω) ? F ? ? ? 26 College of Computer Science amp。 Technology, BUPT S t a r tp r0 , 10q1(1) S t a r tp0 , 11q r0 , 1(2) p q ? r 0 { q } ? { q } ? { q, r } ? 1 p q ? r 0 { p } { r } ? { r } ? 1 { p, q } 轉(zhuǎn)移圖和轉(zhuǎn)移表表示的 NFA 注意：轉(zhuǎn)移表中的每一項(xiàng)都是一個集合。 分析：如果一個十進(jìn)制數(shù)的所有位的數(shù)字之和能整除 3，則該十進(jìn)制數(shù)就能整除 3。 ? 技巧：假設(shè)自己是機(jī)器，思考如何去實(shí)現(xiàn)機(jī)器的任務(wù) 。 Technology, BUPT 五、格局 ? 為描述有限自動機(jī)的工作過程 ， 對于它在某一時刻的工作狀態(tài) ， 可用兩個信息表明：當(dāng)前狀態(tài) q， 待輸入字符串 ω。 Technology, BUPT 四、 擴(kuò)展轉(zhuǎn)移函數(shù)適合于輸入字符串 δ’函數(shù)： 接收一個字符串的狀態(tài)轉(zhuǎn)移函數(shù) 。 Technology, BUPT FA 的模型 FA可以理解成一個控制器 ,它讀一條輸入帶上的字符。 Technology, BUPT 第一節(jié) 有限自動機(jī) ? 實(shí)例 一個人帶著一頭狼 ， 一頭羊 ， 以及一棵青菜 ， 處于河的左岸 。 Technology, BUPT 第三章 有限自動機(jī)與右線性文法 本章主要內(nèi)容 ? 確定有限自動機(jī) ? 非確定有限自動機(jī) ? 確定與非確定有限自動機(jī)的等價性 ? 右線性文法和有限自動機(jī)的等價性 ， ? 右線性文法的性質(zhì) (泵浦定理 ) ? 使用歸納法進(jìn)行證明的方法。 然而如果人留下狼和羊不論在左岸還是在右岸 ， 狼肯定會吃掉羊 。 (3) 狀態(tài) +激勵 ? 狀態(tài)遷移 (根據(jù)當(dāng)前所處狀態(tài)和輸入字符進(jìn)行狀態(tài)轉(zhuǎn)移 ) 7 College of Computer Science amp。為了方便，以后在不引起混淆時用 δ代替 δ39。 Technology, BUPT ? 如圖，接受 001010的格局 （ q0,001010） ┝ (q2,01010) ┝ (q0,1010) ┝ (q1,010) ┝ (q3,10) ┝ (q2,0) ┝ (q0,ε) ? 格局?jǐn)?shù)量是無限的。 關(guān)鍵 ： 不需要記住所看到的整個字符串，只需記住至此所看到的 a、 b個數(shù)是偶數(shù)還是奇數(shù)。 狀態(tài) q0表示已讀入的數(shù)字和除 3余 0, 狀態(tài) q1表示已讀入的數(shù)字和除 3余 1, 狀態(tài) q2表示已讀入的數(shù)字和除 3余 2, q2q1122120q 001019 College of Computer Science amp。 Technology, BUPT 二 、 NFA的狀態(tài)轉(zhuǎn)移函數(shù) ?與 DFA 唯一不同之處 ? : Q ? T ? 2Q 同樣 , δ可擴(kuò)展為 δ’ ( ??: Q ? T* ? 2Q) 39。 2. 證明 : ? 策略 :對于任意一個 NFA,構(gòu)造一個接收它所能接收語言的 DFA， 這個 DFA的狀態(tài)對應(yīng) 了 NFA的狀態(tài)集
電大資料相關(guān)推薦
鄂ICP備17016276號-1