形式語言與自動(dòng)機(jī)-2015-第03講-有窮自動(dòng)機(jī)(1)

1、形式語言與自動(dòng)機(jī)形式語言與自動(dòng)機(jī)Formal Languages and Automata Theory教師：康建初、胡春明、教師：康建初、胡春明、趙永望趙永望http:/ 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)第三章第三章 有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī) FA FA 定義與表示定義與表示二、確定的有窮自動(dòng)機(jī)二、確定的有窮自動(dòng)機(jī) DFADFA三、非確定的有窮自動(dòng)機(jī)三、非確定的有窮自動(dòng)機(jī) NFANFA四、四、DFA DFA 和和 NFA NFA 的等價(jià)性的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)五、帶空移動(dòng)的有窮自動(dòng)機(jī)- NFA- NFA六、六、FA FA 是正則語言的識(shí)別器是正則語言的識(shí)

2、別器 七、七、FA FA 的變形的變形 - - 帶輸出的帶輸出的 FAFA第第一一次課次課第二第二次課次課語言的識(shí)別語言的識(shí)別方法方法1：根據(jù)：根據(jù)G的定義，尋找一個(gè)派生，或歸約的定義，尋找一個(gè)派生，或歸約一、有窮狀態(tài)自動(dòng)機(jī)定義與表示一、有窮狀態(tài)自動(dòng)機(jī)定義與表示自動(dòng)機(jī)系統(tǒng)的自動(dòng)機(jī)系統(tǒng)的結(jié)構(gòu)及功能特征分析結(jié)構(gòu)及功能特征分析： 1 1、字母表：系統(tǒng)處理的所有字符串由字母表上的字符組成；、字母表：系統(tǒng)處理的所有字符串由字母表上的字符組成；2 2、控制器：系統(tǒng)每次從輸入字符串讀入一個(gè)字符，并根據(jù)當(dāng)前狀態(tài)、控制器：系統(tǒng)每次從輸入字符串讀入一個(gè)字符，并根據(jù)當(dāng)前狀態(tài)和讀入的字符，轉(zhuǎn)入新的狀態(tài)；新的狀態(tài)和當(dāng)前

3、狀態(tài)可以相同也可不和讀入的字符，轉(zhuǎn)入新的狀態(tài)；新的狀態(tài)和當(dāng)前狀態(tài)可以相同也可不同；為此，系統(tǒng)具有有窮個(gè)狀態(tài)同；為此，系統(tǒng)具有有窮個(gè)狀態(tài), ,并需要維護(hù)一個(gè)讀指針。并需要維護(hù)一個(gè)讀指針。3 3、幾個(gè)特殊狀態(tài)：、幾個(gè)特殊狀態(tài)： 一個(gè)開始狀態(tài)；系統(tǒng)從此開始處理句子；一個(gè)開始狀態(tài)；系統(tǒng)從此開始處理句子； 一些稱之為終止?fàn)顟B(tài)或接受狀態(tài)，系統(tǒng)從開始狀態(tài)至此狀態(tài)為一些稱之為終止?fàn)顟B(tài)或接受狀態(tài)，系統(tǒng)從開始狀態(tài)至此狀態(tài)為止，讀入字符構(gòu)成的字符串是語言的一個(gè)句子；系統(tǒng)到達(dá)這些止，讀入字符構(gòu)成的字符串是語言的一個(gè)句子；系統(tǒng)到達(dá)這些狀態(tài)讀入的全部字符串構(gòu)成系統(tǒng)所能識(shí)別的語言。狀態(tài)讀入的全部字符串構(gòu)成系統(tǒng)所能識(shí)別的語言

4、。有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)裝置的物理模型：有窮狀態(tài)自動(dòng)機(jī)裝置的物理模型： 有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)裝置的組成：有窮狀態(tài)自動(dòng)機(jī)裝置的組成： 1、一個(gè)具有一系列方格的輸入字符串的帶子：方格中存放字、一個(gè)具有一系列方格的輸入字符串的帶子：方格中存放字符，字符從輸入帶左端開始存放，符，字符從輸入帶左端開始存放，輸入帶右端無窮輸入帶右端無窮； 2、一個(gè)有窮狀態(tài)控制器、一個(gè)有窮狀態(tài)控制器 FSC：控制一個(gè)讀頭；每讀入一個(gè)字：控制一個(gè)讀頭；每讀入一個(gè)字符，讀頭右移一格，指向下一個(gè)待讀入字符。符，讀頭右移一格，指向下一個(gè)待讀入字符。有

5、窮狀態(tài)控制器有窮狀態(tài)控制器 FSC 的基本工作過程：的基本工作過程： 控制器執(zhí)行動(dòng)作由三個(gè)節(jié)拍組成：控制器執(zhí)行動(dòng)作由三個(gè)節(jié)拍組成： 讀頭讀入當(dāng)前指向的字讀頭讀入當(dāng)前指向的字符；符； 根據(jù)讀入的字符和其自身當(dāng)前狀態(tài)，改變有窮狀態(tài)控制根據(jù)讀入的字符和其自身當(dāng)前狀態(tài)，改變有窮狀態(tài)控制器的狀態(tài)；器的狀態(tài)； 讀頭右移一格指向下一個(gè)字符。讀頭右移一格指向下一個(gè)字符。有窮狀態(tài)自動(dòng)機(jī)定義與表示有窮狀態(tài)自動(dòng)機(jī)定義與表示8有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示(q0, 0)=q1 (q0, 1) = q3 (q0, 2) = q3 (q1, 0)=q2 (q1, 1) = q3 (q1, 2) = q3

6、 (q2, 0)=q1 (q2, 1) = q3 (q2, 2) = q3 (q3, 0)=q3 (q3, 1) = q3 (q3, 2) = q3 狀態(tài)表表示法：狀態(tài)表表示法：狀態(tài)圖表示法：狀態(tài)圖表示法：q0q3q1q2 1, 2 1, 2 1,2 00 0,1,2 0012狀態(tài)說明狀態(tài)說明q0q1q3q3 開始狀態(tài)開始狀態(tài)q1q2q3q3q2q1q3q3終止?fàn)顟B(tài)終止?fàn)顟B(tài)q3q3q3q3有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)定義與定義與表示表示函數(shù)表示法：函數(shù)表示法：有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)定義與表示定義與表示注：狀態(tài)轉(zhuǎn)移圖中可能存在一些并行弧，其從同一節(jié)點(diǎn)出發(fā)，到達(dá)同注：狀態(tài)轉(zhuǎn)移圖中可能存在一些

7、并行弧，其從同一節(jié)點(diǎn)出發(fā)，到達(dá)同一節(jié)點(diǎn)。一節(jié)點(diǎn)。11一個(gè)例子一個(gè)例子:分析：目標(biāo)是構(gòu)造一個(gè)分析：目標(biāo)是構(gòu)造一個(gè)DFA，識(shí)別串，識(shí)別串x是是否有連續(xù)的否有連續(xù)的3個(gè)個(gè)0作為結(jié)尾作為結(jié)尾.狀態(tài)狀態(tài)0. 目目前已經(jīng)讀入了前已經(jīng)讀入了0個(gè)個(gè)0，即，即 xxxx1或或1狀態(tài)狀態(tài)1. 目目前已經(jīng)讀入了前已經(jīng)讀入了1個(gè)個(gè)0，即，即 xxxx10或或0狀態(tài)狀態(tài)2. 目目前已經(jīng)讀入了前已經(jīng)讀入了2個(gè)個(gè)0，即，即 xxxx100或或00狀態(tài)狀態(tài)3. 目目前已經(jīng)讀入了前已經(jīng)讀入了3個(gè)個(gè)0，即，即 xxxx1000或或0000001S1有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示關(guān)于關(guān)于 FA 的幾個(gè)基本概念：的

8、幾個(gè)基本概念：1、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)、基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)2、FA 的瞬時(shí)（即時(shí)）描述的瞬時(shí)（即時(shí)）描述3、FA 狀態(tài)對(duì)讀入字符串的存儲(chǔ)功能狀態(tài)對(duì)讀入字符串的存儲(chǔ)功能4、何謂、何謂 FA 識(shí)別一個(gè)句子或語言識(shí)別一個(gè)句子或語言5、FA 的等價(jià)性的等價(jià)性有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示（與表示（1）定義定義3.1的補(bǔ)充定義：的補(bǔ)充定義：有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示讀入空串讀入空串讀入非空串讀入非空串對(duì)于任意的對(duì)于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a

9、 ) = ( ( ( q, a1 ), a2 ), an ), a ) 說明說明 1 1：DFA DFA 從狀態(tài)從狀態(tài) q q 出發(fā)處理字符串出發(fā)處理字符串 wa 的狀態(tài)轉(zhuǎn)移過程：的狀態(tài)轉(zhuǎn)移過程：有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示說明說明 2：由于由于 Q是是 Q* 的真子集；對(duì)于任意輸入字符的真子集；對(duì)于任意輸入字符 a，有，有 ( q, a ) = ( q, a ) 是單位元素是單位元素 = ( ( q, ), a ) 由補(bǔ)充定義第由補(bǔ)充定義第 2 條條 =( q, a ) 由補(bǔ)充定義第由補(bǔ)充定義第 1 條條有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示可見，狀態(tài)轉(zhuǎn)移函數(shù)可

10、見，狀態(tài)轉(zhuǎn)移函數(shù) 可以涵蓋描述可以涵蓋描述 ，因此，不必區(qū)分的，因此，不必區(qū)分的使用使用和和 ，通常一般性地用，通常一般性地用代替代替 。定義定義 3.3：設(shè)設(shè) FA M = ( Q, , , q0, F )，x, y*，( q0, x ) = q , x q y 稱為稱為 M 的一個(gè)瞬時(shí)描述（的一個(gè)瞬時(shí)描述（ID），）， 表示：表示：xy 是是 M 正在處理的一個(gè)字符串，其子串正在處理的一個(gè)字符串，其子串 x 引導(dǎo)引導(dǎo) M 從從 q0 啟動(dòng)，到達(dá)狀態(tài)啟動(dòng)，到達(dá)狀態(tài) q, M 的讀頭當(dāng)前指向子串的讀頭當(dāng)前指向子串 y 的首的首字符。字符。有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示（與表示（2）

11、如果如果 xqay 是是 M 一個(gè)瞬時(shí)描述一個(gè)瞬時(shí)描述, 且且 （ q, a ）= p ，則有：，則有： xqay xapy 表示表示 M 在狀態(tài)在狀態(tài) q 時(shí)已處理完字符串時(shí)已處理完字符串 x；當(dāng)前讀入的字符為；當(dāng)前讀入的字符為 a且轉(zhuǎn)入狀態(tài)且轉(zhuǎn)入狀態(tài) p, 然后將讀頭向右移動(dòng)一格，指向字符串然后將讀頭向右移動(dòng)一格，指向字符串 y 的首字符。的首字符。MFA M 的瞬時(shí)移動(dòng)描述：的瞬時(shí)移動(dòng)描述：有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示FA M 的瞬時(shí)移動(dòng)序列描述的瞬時(shí)移動(dòng)序列描述： ：M 從已識(shí)別的字符串從已識(shí)別的字符串 出發(fā)，經(jīng)過出發(fā)，經(jīng)過 n 次移動(dòng)，次移動(dòng)，識(shí)別的字符串變?yōu)樽R(shí)別

12、的字符串變?yōu)?；亦即，存在；亦即，存在 n 個(gè)個(gè) ID 構(gòu)成序列：構(gòu)成序列： , 1, 2, , n-1, ，使得使得 1 . n-1 。nMMMMM有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示例：例： q0 abc a q1 bc abc q3注：所有移動(dòng)都在注：所有移動(dòng)都在 M 中進(jìn)行時(shí)，可省去中進(jìn)行時(shí)，可省去 推導(dǎo)符中的推導(dǎo)符中的 M，分別記為：，分別記為：n幾個(gè)特殊的瞬時(shí)移動(dòng)序列描述：幾個(gè)特殊的瞬時(shí)移動(dòng)序列描述： ：M 的的 ID 從從 出發(fā)，經(jīng)過若干步（包含零步）移動(dòng)，出發(fā)，經(jīng)過若干步（包含零步）移動(dòng)，變成變成 。 ：M 的的 ID 從從 出發(fā)，經(jīng)過至少一步移動(dòng)，變成出發(fā)，經(jīng)過至

13、少一步移動(dòng)，變成 。 M+M ：n = 0 , = 。nM （M 沒有移動(dòng)）沒有移動(dòng)）有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示FA M 瞬時(shí)移動(dòng)序列描述實(shí)例：瞬時(shí)移動(dòng)序列描述實(shí)例：例：例：FA M 識(shí)別輸入串識(shí)別輸入串1010010001，產(chǎn)生一，產(chǎn)生一 個(gè)瞬時(shí)移動(dòng)描述序列：個(gè)瞬時(shí)移動(dòng)描述序列：有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示 有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示（與表示（3）定義定義 3-4：設(shè)有限自動(dòng)機(jī)設(shè)有限自動(dòng)機(jī) FA M = , 對(duì)于對(duì)于 q Q，能引導(dǎo)，能引導(dǎo) FA 從開始狀態(tài)到達(dá)從開始狀態(tài)到達(dá) q 的字符串集合的字符串集合 set ( q ) = x

14、| x * 且且( q0, x ) = q 定義為狀態(tài)定義為狀態(tài) q 對(duì)對(duì)字符串的存儲(chǔ)能力字符串的存儲(chǔ)能力。例：接受語言例：接受語言 L= x000 | x 0,1* x001 | x 0,1* 的的 FA M 各狀態(tài)的字各狀態(tài)的字符串存儲(chǔ)能力如下：符串存儲(chǔ)能力如下：set (q0) = x | x *, x = 或者或者 x 以以 1 結(jié)尾但不以結(jié)尾但不以 001 結(jié)尾結(jié)尾 ;set (q1) = x | x *, x = 0 或者或者 x 以以 10 結(jié)尾結(jié)尾 set (q2) = x | x *, x = 00 或者或者 x 以以 100 結(jié)尾結(jié)尾 set (q3) = x | x *,

15、 x 僅以僅以 000 結(jié)尾結(jié)尾 set (q4) = x | x *, x 僅以僅以 001 結(jié)尾結(jié)尾 L = x000 | x 0,1* x001 | x 0,1 * set (q0) = x | x *, x = 或者或者 x 以以 1 結(jié)尾但不以結(jié)尾但不以 001 結(jié)尾結(jié)尾 ;set (q1) = x | x *, x = 0 或者或者 x 以以 10 結(jié)尾結(jié)尾 set (q2) = x | x *, x = 00 或者或者 x 以以 100 結(jié)尾結(jié)尾 set (q3) = x | x *, x 僅以僅以 000 結(jié)尾結(jié)尾 set (q4) = x | x *, x 僅以僅以 001

16、結(jié)尾結(jié)尾 有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示與表示說明：說明：1、上述、上述 5 個(gè)集合兩兩互不相交；個(gè)集合兩兩互不相交；5 個(gè)集合的并正好構(gòu)成個(gè)集合的并正好構(gòu)成 M 識(shí)別輸入字母識(shí)別輸入字母表表 0，1 的克林閉包；亦即，這的克林閉包；亦即，這 5 個(gè)集合是關(guān)于個(gè)集合是關(guān)于 0, 1 * 的一個(gè)劃分；的一個(gè)劃分；2、此劃分可由、此劃分可由 M 上的一個(gè)等價(jià)關(guān)系上的一個(gè)等價(jià)關(guān)系 RM 確定，亦即，確定，亦即， x, y *， x RM y q Q, x, y set ( q )有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示（與表示（4）定義定義 3-6： 設(shè)設(shè) M1，M2 是是 FA。如果

17、。如果 L（M1）= L（M2），則），則稱稱M1 與與 M2 等價(jià)。等價(jià)。有窮狀態(tài)自動(dòng)機(jī)定義有窮狀態(tài)自動(dòng)機(jī)定義與表示（與表示（5）第三章第三章 有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī) FA FA 定義與表示定義與表示二、確定的有窮自動(dòng)機(jī)二、確定的有窮自動(dòng)機(jī) DFADFA三、非確定的有窮自動(dòng)機(jī)三、非確定的有窮自動(dòng)機(jī) NFANFA四、四、DFA DFA 和和 NFA NFA 的等價(jià)性的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)五、帶空移動(dòng)的有窮自動(dòng)機(jī)- NFA- NFA六、六、FA FA 是正則語言的識(shí)別器是正則語言的識(shí)別器 七、七、FA FA 的變形的變形 - - 帶輸出的帶輸出

18、的 FAFA定義定義 3-7： 確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī) ，記作，記作 DFA，為一個(gè)五元組，為一個(gè)五元組 M = ，其中，其中， Q， q0，F(xiàn) 的意義與的意義與 FA 定義相同；定義相同； 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù): Q Q 為單值映射函數(shù)，即，對(duì)為單值映射函數(shù)，即，對(duì) q Q 和和 a , (q, a) = p 有唯一映射值；有唯一映射值；M 在狀態(tài)在狀態(tài) q 下讀入字符下讀入字符 a， 將狀態(tài)將狀態(tài) q 變成唯一狀態(tài)變成唯一狀態(tài) p，讀頭向右移，讀頭向右移動(dòng)一個(gè)方格，指向輸入字符串的下一個(gè)字符。動(dòng)一個(gè)方格，指向輸入字符串的下一個(gè)字符。 二、確定的有窮自動(dòng)機(jī)二、確定的有窮自動(dòng)機(jī)

19、DFADFA例例1：構(gòu)造一構(gòu)造一DFM，使它接受語言，使它接受語言 L= x000y | x, y 0, 1 * 。語言句子結(jié)構(gòu)特征分析：語言句子結(jié)構(gòu)特征分析：對(duì)于任給輸入字符串對(duì)于任給輸入字符串 x 0, 1 *，DFA M 需逐一檢查需逐一檢查 x 的每個(gè)的每個(gè)字符，判斷其中是否存在連續(xù)的字符，判斷其中是否存在連續(xù)的 000 作為子串，有則接受作為子串，有則接受 x,然然后，繼續(xù)讀完字符串剩余的后綴后，繼續(xù)讀完字符串剩余的后綴 y。確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFAFA 的主框架分析的主框架分析 ： q0：M 的開始狀態(tài)；的開始狀態(tài)； q1： M在在 q q0 0 后讀入后讀入

20、一個(gè)一個(gè) 0，其可能是子串，其可能是子串 000 的第一個(gè)的第一個(gè) 0，記?。?，記??； q2 ：M 在在 q1 后又讀入一個(gè)后又讀入一個(gè) 0，其可能是子串，其可能是子串 000 的第二個(gè)的第二個(gè) 0，記??；，記?。?q3：M 在在q2后又讀入一個(gè)后又讀入一個(gè) 0，發(fā)現(xiàn)了子串，發(fā)現(xiàn)了子串 000 ，記住，此狀態(tài)為終態(tài)。，記住，此狀態(tài)為終態(tài)。設(shè)計(jì)設(shè)計(jì) 補(bǔ)足補(bǔ)足 FA 所缺失的其它狀態(tài)：所缺失的其它狀態(tài)： (q0, 0) = q1 可能讀到可能讀到 x 第一個(gè)第一個(gè) 0； (q0, 1) = q0 回始態(tài)重新檢查；回始態(tài)重新檢查； (q1, 0) = q2 可能讀到可能讀到 x 第二個(gè)第二個(gè) 0；

21、(q1, 1) = q0 - 回始態(tài)重新檢查；回始態(tài)重新檢查； (q2, 0) = q3 發(fā)現(xiàn)發(fā)現(xiàn) x 的子串的子串 000； (q2, 1) = q0 - 回始態(tài)重新檢查；回始態(tài)重新檢查； (q3, 0) = q3 ， (q3, 1) = q3 - 已到達(dá)終態(tài)，繼續(xù)接受字符串的后綴。已到達(dá)終態(tài)，繼續(xù)接受字符串的后綴。 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA定義控制器的有限狀態(tài)：定義控制器的有限狀態(tài)：狀狀 態(tài)態(tài) 表表狀狀 態(tài)態(tài) 圖圖確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFADFADFA識(shí)別字符識(shí)別字符下面哪個(gè)是自動(dòng)機(jī)可識(shí)別的字符？下面哪個(gè)是自動(dòng)機(jī)可識(shí)別的字符？A. epsilonB

22、. 011C. 100011D. 1011ABCD011100所識(shí)別語言中同一長(zhǎng)度的字符數(shù)所識(shí)別語言中同一長(zhǎng)度的字符數(shù)這個(gè)自動(dòng)機(jī)可接受的長(zhǎng)度最小的字符是這個(gè)自動(dòng)機(jī)可接受的長(zhǎng)度最小的字符是2，共有兩個(gè)，共有兩個(gè)，01和和10。記作。記作 N(2)=2. 請(qǐng)問：請(qǐng)問：A. N(13)=16B. N(13)=84C. N(12)=14D. N(12)=624ABCD011100解：解：DFM 可定義為：可定義為： M =（ q0, q1, q2, q3 , 0, 1 , (q0, 0) = q1, (q1, 0) = q2, (q2, 0)= q3,(q3, 0)= q3,(q0, 1) = q0,

23、 (q1, 1)= q0, (q2, 1)= q0, (q3, 1)= q3 , q0， q3 ）。）。例例1：構(gòu)造一構(gòu)造一DFM，使它接受語言，使它接受語言 L= x000y | x, y 0, 1 * 。確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA例例2： 構(gòu)造一構(gòu)造一DFM，使其接受語言，使其接受語言 L= 0n1m2k | n, m, k 1 。語言句子結(jié)構(gòu)特征語言句子結(jié)構(gòu)特征分析分析：0 在最前，在最前，1 在中間，在中間，2在最后，三者不可交叉出現(xiàn)；不可顛在最后，三者不可交叉出現(xiàn)；不可顛倒順序；字符倒順序；字符 0、1、2 的個(gè)數(shù)均不得少于的個(gè)數(shù)均不得少于 1。確定的有窮自動(dòng)機(jī)確

24、定的有窮自動(dòng)機(jī) DFADFAFA 的主框架分析的主框架分析： q0：M 的開始狀態(tài)；的開始狀態(tài)； q1： M在在 q0 后讀到至少一個(gè)后讀到至少一個(gè) 0，等待讀入更多個(gè)，等待讀入更多個(gè) 0； q2 ：M 在在 q1 后讀入至少一個(gè)后讀入至少一個(gè) 1，等待讀入更多個(gè)，等待讀入更多個(gè) 1； q3：M 在在 q2 后讀入至少一個(gè)后讀入至少一個(gè) 2，等待讀入更多個(gè)，等待讀入更多個(gè) 1 ，此狀態(tài)為終態(tài)。，此狀態(tài)為終態(tài)。確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA求識(shí)別求識(shí)別 L= 0n1m2k | n, m, k 1 的的 DFA M補(bǔ)足補(bǔ)足 FA 缺失部分：缺失部分： - 引入陷阱狀態(tài)引入陷阱狀態(tài)

25、qt (自鎖態(tài)自鎖態(tài))：系系統(tǒng)一旦進(jìn)入則無法離開的狀態(tài)。統(tǒng)一旦進(jìn)入則無法離開的狀態(tài)。設(shè)計(jì)要點(diǎn)：設(shè)計(jì)要點(diǎn)：1、構(gòu)造一個(gè)識(shí)別給定語言的、構(gòu)造一個(gè)識(shí)別給定語言的 DFA 時(shí)，可先根據(jù)語言的主要特征，畫時(shí)，可先根據(jù)語言的主要特征，畫出該出該FA的主體框架圖，然后考慮相關(guān)細(xì)節(jié)問題。的主體框架圖，然后考慮相關(guān)細(xì)節(jié)問題。2、一旦、一旦 DFA 發(fā)現(xiàn)無法識(shí)別的語言句子，則進(jìn)入陷阱狀態(tài)發(fā)現(xiàn)無法識(shí)別的語言句子，則進(jìn)入陷阱狀態(tài) qt；引入陷；引入陷阱狀態(tài)可方便阱狀態(tài)可方便 FA 的構(gòu)造。的構(gòu)造。 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA確定的有窮自動(dòng)機(jī)確定的有窮自

26、動(dòng)機(jī) DFADFA 注注意：意：M的每個(gè)狀態(tài)給出了語言的等價(jià)類，所有狀態(tài)構(gòu)成了語言的每個(gè)狀態(tài)給出了語言的等價(jià)類，所有狀態(tài)構(gòu)成了語言上的一個(gè)劃分上的一個(gè)劃分 分析：什么是這里的分析：什么是這里的“有窮狀態(tài)有窮狀態(tài)”？（或者等價(jià)類）？（或者等價(jià)類）確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA 注注意：意：M的每個(gè)狀態(tài)給出了語言的等價(jià)類，所有狀態(tài)構(gòu)成了語言的每個(gè)狀態(tài)給出了語言的等價(jià)類，所有狀態(tài)構(gòu)成了語言上的一個(gè)劃分上的一個(gè)劃分 分析：什么是這里的分析：什么是這里的“有窮狀態(tài)有窮狀態(tài)”？（或者等價(jià)類）？（或者等價(jià)類）這些等價(jià)類之間如何轉(zhuǎn)換？（這些等價(jià)類之間如何轉(zhuǎn)換？（ x xa意味著意味著 xa=

27、2*x + a）確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī) DFADFA 分析：什么是這里的分析：什么是這里的“有窮狀態(tài)有窮狀態(tài)”？小結(jié)：小結(jié)：1、有窮自動(dòng)機(jī)、有窮自動(dòng)機(jī) FA 的一般概念：的一般概念： 自動(dòng)機(jī)定義自動(dòng)機(jī)定義 五元組：五元組： M = ； 自動(dòng)機(jī)表示方法：函數(shù)法，狀態(tài)表，狀態(tài)圖；自動(dòng)機(jī)表示方法：函數(shù)法，狀態(tài)表，狀態(tài)圖； FA 的瞬時(shí)移動(dòng)序列描述：的瞬時(shí)移動(dòng)序列描述：xqay xapy 及及 n 次移動(dòng)合成；次移動(dòng)合成； FA 每個(gè)狀態(tài)對(duì)讀入字符串均具有某種存儲(chǔ)功能：每個(gè)狀態(tài)對(duì)讀入字符串均具有某種存儲(chǔ)功能：set ( q )； 能為能為 FA

28、接受的語言；接受的語言；FA 的等價(jià)等。的等價(jià)等。2、確定型有窮自動(dòng)機(jī)、確定型有窮自動(dòng)機(jī) DFA 的定義及其構(gòu)造：的定義及其構(gòu)造： 定義：定義：DFA 的狀態(tài)轉(zhuǎn)移函數(shù)的狀態(tài)轉(zhuǎn)移函數(shù) 唯一；唯一； 構(gòu)造：首先，根據(jù)語言結(jié)構(gòu)特征設(shè)計(jì)構(gòu)造：首先，根據(jù)語言結(jié)構(gòu)特征設(shè)計(jì) DFA 主框架，然后，運(yùn)用主框架，然后，運(yùn)用其它未明示的信息補(bǔ)足其它未明示的信息補(bǔ)足主框架主框架設(shè)計(jì)；設(shè)計(jì)中可增設(shè)設(shè)計(jì)；設(shè)計(jì)中可增設(shè)“陷阱狀態(tài)陷阱狀態(tài)”。M第三章第三章 有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī)一、有窮狀態(tài)自動(dòng)機(jī) FA FA 定義與表示定義與表示二、確定的有窮自動(dòng)機(jī)二、確定的有窮自動(dòng)機(jī) DFADFA三、非確定的有窮

29、自動(dòng)機(jī)三、非確定的有窮自動(dòng)機(jī) NFANFA四、四、DFA DFA 和和 NFA NFA 的等價(jià)性的等價(jià)性五、帶空移動(dòng)的有窮自動(dòng)機(jī)五、帶空移動(dòng)的有窮自動(dòng)機(jī)- NFA- NFA六、六、FA FA 是正則語言的識(shí)別器是正則語言的識(shí)別器 七、七、FA FA 的變形的變形 - - 帶輸出的帶輸出的 FAFA例例 3：求接受語言求接受語言 L（M）= x | x 0,1 *，且，且 x 含有子串含有子串 00 或或 11 的的 FA。狀態(tài)表狀態(tài)表狀態(tài)圖狀態(tài)圖三、非確定有窮自動(dòng)機(jī)三、非確定有窮自動(dòng)機(jī) NFANFA3、此時(shí)的、此時(shí)的N FA 程序應(yīng)視為擁有程序應(yīng)視為擁有“智能智能” ，亦即，在一給定，亦即，在

30、一給定狀態(tài)下，它可根據(jù)當(dāng)前從輸入字符串讀入的字符自動(dòng)到狀態(tài)下，它可根據(jù)當(dāng)前從輸入字符串讀入的字符自動(dòng)到( q, a ) 的轉(zhuǎn)移狀態(tài)的轉(zhuǎn)移狀態(tài)集合集合中選擇進(jìn)入一個(gè)正確的狀態(tài)。中選擇進(jìn)入一個(gè)正確的狀態(tài)。非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī) NFANFA非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī) NFANFA幾個(gè)相關(guān)的基本概念：幾個(gè)相關(guān)的基本概念：1、引入基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)、引入基于字符串的狀態(tài)轉(zhuǎn)移函數(shù)；2、 NFA 接受句子及語言的條件接受句子及語言的條件3、兩個(gè)、兩個(gè) NFA 的等價(jià)的等價(jià)非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī) NFANFA非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī) NFANFA非確定有窮自動(dòng)機(jī)非確定

31、有窮自動(dòng)機(jī) NFANFA定義定義 3-8 的補(bǔ)充：的補(bǔ)充： 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)擴(kuò)展為擴(kuò)展為 對(duì)于任意的對(duì)于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a ) = ( ( ( q, a1 ), a2 ), an ), a ) 非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī) NFANFA說明說明 1 1：NFA NFA 從狀態(tài)從狀態(tài) q q 出發(fā)處理字符串出發(fā)處理字符串 wa 狀態(tài)轉(zhuǎn)移過程：狀態(tài)轉(zhuǎn)移過程：說明說明 2：由于由于 Q是是 Q* 的真子集；對(duì)于任意的的真子集；對(duì)于任意的 q Q，a ，有，有 ( q，a ) = ( q，a ) 是單位元素是單位元素 = pr ( q，)，使得，使得 p ( r, a ) 由定義第由定義第 2 條條 = pr q ，