week2-第三章-有限自動(dòng)機(jī)(編輯修改稿)
2025-08-20 16:18 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ,1111)。 格局示例 q0 q1 q2 q3 S t a r t0110110016 College of Computer Science amp。 Technology, BUPT 設(shè)計(jì)有限自動(dòng)機(jī) ? 自動(dòng)機(jī)的設(shè)計(jì)是一個(gè)創(chuàng)造過(guò)程，沒(méi)有簡(jiǎn)單的算法或過(guò)程。 ? 技巧：假設(shè)自己是機(jī)器，思考如何去實(shí)現(xiàn)機(jī)器的任務(wù) 。 ? 為判斷到目前為止所看到的字符串是否滿足某個(gè)語(yǔ)言，須估算出讀一個(gè)字符串時(shí)需要記住哪些關(guān)鍵的東西。 例： 構(gòu)造自動(dòng)機(jī)，識(shí)別所有由奇數(shù)個(gè) a和奇數(shù)個(gè) b組成的字符串。 關(guān)鍵 ： 不需要記住所看到的整個(gè)字符串，只需記住至此所看到的 a、 b個(gè)數(shù)是偶數(shù)還是奇數(shù)。 q偶 a偶 b q奇 a偶 b q偶 a奇 b q奇 a奇 b Start b a a b a a b b 17 College of Computer Science amp。 Technology, BUPT 設(shè)計(jì)有限自動(dòng)機(jī) ? 例 2：構(gòu)造有限自動(dòng)機(jī) M，識(shí)別 {0,1}上的語(yǔ)言 ? L={x000y | x,y∈ {0,1}*} ? 分析：該語(yǔ)言特點(diǎn)是每個(gè)串都包含連續(xù) 3個(gè) 0的子串，自動(dòng)機(jī)的任務(wù)是識(shí)別 /檢查是否存在子串 000。 由于字符是逐一讀入，當(dāng)讀入一個(gè) 0時(shí)，就需記?。顟B(tài) q1), 若接著讀入的還是 0，則需記住已讀入連續(xù)的 2個(gè) 0了（狀態(tài) q2),若接著讀入的還是 0，則需記住已讀入連續(xù)的 3個(gè) 0了（狀態(tài) q3), q3q0q1q20 0 01110 , 118 College of Computer Science amp。 Technology, BUPT 設(shè)計(jì)有限自動(dòng)機(jī) 例 3：構(gòu)造有限自動(dòng)機(jī) M，識(shí)別 {0,1,2}上的語(yǔ)言 ,每個(gè)字符串代表的數(shù)字能整除 3。 分析：如果一個(gè)十進(jìn)制數(shù)的所有位的數(shù)字之和能整除 3，則該十進(jìn)制數(shù)就能整除 3。 一個(gè)十進(jìn)制數(shù)除以 3，余數(shù)只能為 0、 2。 設(shè)計(jì)為狀態(tài)。 狀態(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 第二節(jié) 不確定的有限自動(dòng)機(jī) (NFA) 修改 DFA的模型 ,使之在某個(gè)狀態(tài) , 對(duì)應(yīng)一個(gè)輸入 ,可以有多個(gè)轉(zhuǎn)移 , 到達(dá)不 同的狀態(tài) , 即：具有在同一情況下可有不同選擇的能力 。則稱為不確定的有限自動(dòng)機(jī)。 例： S t a r tp r0 , 10q1(1) S t a r tp0 , 11q r0 , 1(2) 20 College of Computer Science amp。 Technology, BUPT 一、不確定有限自動(dòng)機(jī)的形式定義 ? NFA是一個(gè)五元組 ,M=(Q,T,δ,q0,F). 其中 δ是 Q T2Q的函數(shù) ,其余與 DFA相同 . ? 如果接收一個(gè)字符串后 NFA進(jìn)入一個(gè)狀態(tài)集 ,而此集合中包含 一個(gè)以上 F中的狀態(tài) , 則 稱NFA接收該字符串 . 21 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)都是一個(gè)集合。含空集 Φ 22 College of Computer Science amp。 Technology, BUPT ? 例：構(gòu)造 NFA，可識(shí)別 {0,1}上的語(yǔ)言
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1