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

2、別器 七、七、FA FA 的變形的變形 - - 帶輸出的帶輸出的 FAFA第第一一次課次課第二第二次課次課語言的識別語言的識別方法方法1：根據：根據G的定義，尋找一個派生，或歸約的定義，尋找一個派生，或歸約一、有窮狀態自動機定義與表示一、有窮狀態自動機定義與表示自動機系統的自動機系統的結構及功能特征分析結構及功能特征分析： 1 1、字母表：系統處理的所有字符串由字母表上的字符組成；、字母表：系統處理的所有字符串由字母表上的字符組成；2 2、控制器：系統每次從輸入字符串讀入一個字符，并根據當前狀態、控制器：系統每次從輸入字符串讀入一個字符，并根據當前狀態和讀入的字符，轉入新的狀態；新的狀態和當前

3、狀態可以相同也可不和讀入的字符，轉入新的狀態；新的狀態和當前狀態可以相同也可不同；為此，系統具有有窮個狀態同；為此，系統具有有窮個狀態, ,并需要維護一個讀指針。并需要維護一個讀指針。3 3、幾個特殊狀態：、幾個特殊狀態： 一個開始狀態；系統從此開始處理句子；一個開始狀態；系統從此開始處理句子； 一些稱之為終止狀態或接受狀態，系統從開始狀態至此狀態為一些稱之為終止狀態或接受狀態，系統從開始狀態至此狀態為止，讀入字符構成的字符串是語言的一個句子；系統到達這些止，讀入字符構成的字符串是語言的一個句子；系統到達這些狀態讀入的全部字符串構成系統所能識別的語言。狀態讀入的全部字符串構成系統所能識別的語言

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

5、窮狀態控制器有窮狀態控制器 FSC 的基本工作過程：的基本工作過程： 控制器執行動作由三個節拍組成：控制器執行動作由三個節拍組成： 讀頭讀入當前指向的字讀頭讀入當前指向的字符；符； 根據讀入的字符和其自身當前狀態，改變有窮狀態控制根據讀入的字符和其自身當前狀態，改變有窮狀態控制器的狀態；器的狀態； 讀頭右移一格指向下一個字符。讀頭右移一格指向下一個字符。有窮狀態自動機定義與表示有窮狀態自動機定義與表示8有窮狀態自動機定義有窮狀態自動機定義與表示與表示(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 狀態表表示法：狀態表表示法：狀態圖表示法：狀態圖表示法：q0q3q1q2 1, 2 1, 2 1,2 00 0,1,2 0012狀態說明狀態說明q0q1q3q3 開始狀態開始狀態q1q2q3q3q2q1q3q3終止狀態終止狀態q3q3q3q3有窮狀態自動機有窮狀態自動機定義與定義與表示表示函數表示法：函數表示法：有窮狀態自動機有窮狀態自動機定義與表示定義與表示注：狀態轉移圖中可能存在一些并行弧，其從同一節點出發，到達同注：狀態轉移圖中可能存在一些

7、并行弧，其從同一節點出發，到達同一節點。一節點。11一個例子一個例子:分析：目標是構造一個分析：目標是構造一個DFA，識別串，識別串x是是否有連續的否有連續的3個個0作為結尾作為結尾.狀態狀態0. 目目前已經讀入了前已經讀入了0個個0，即，即 xxxx1或或1狀態狀態1. 目目前已經讀入了前已經讀入了1個個0，即，即 xxxx10或或0狀態狀態2. 目目前已經讀入了前已經讀入了2個個0，即，即 xxxx100或或00狀態狀態3. 目目前已經讀入了前已經讀入了3個個0，即，即 xxxx1000或或0000001S1有窮狀態自動機定義有窮狀態自動機定義與表示與表示關于關于 FA 的幾個基本概念：的

8、幾個基本概念：1、基于字符串的狀態轉移函數、基于字符串的狀態轉移函數2、FA 的瞬時（即時）描述的瞬時（即時）描述3、FA 狀態對讀入字符串的存儲功能狀態對讀入字符串的存儲功能4、何謂、何謂 FA 識別一個句子或語言識別一個句子或語言5、FA 的等價性的等價性有窮狀態自動機定義有窮狀態自動機定義與表示（與表示（1）定義定義3.1的補充定義：的補充定義：有窮狀態自動機定義有窮狀態自動機定義與表示與表示讀入空串讀入空串讀入非空串讀入非空串對于任意的對于任意的 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 從狀態從狀態 q q 出發處理字符串出發處理字符串 wa 的狀態轉移過程：的狀態轉移過程：有窮狀態自動機定義有窮狀態自動機定義與表示與表示說明說明 2：由于由于 Q是是 Q* 的真子集；對于任意輸入字符的真子集；對于任意輸入字符 a，有，有 ( q, a ) = ( q, a ) 是單位元素是單位元素 = ( ( q, ), a ) 由補充定義第由補充定義第 2 條條 =( q, a ) 由補充定義第由補充定義第 1 條條有窮狀態自動機定義有窮狀態自動機定義與表示與表示可見，狀態轉移函數可

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

11、如果如果 xqay 是是 M 一個瞬時描述一個瞬時描述, 且且 （ q, a ）= p ，則有：，則有： xqay xapy 表示表示 M 在狀態在狀態 q 時已處理完字符串時已處理完字符串 x；當前讀入的字符為；當前讀入的字符為 a且轉入狀態且轉入狀態 p, 然后將讀頭向右移動一格，指向字符串然后將讀頭向右移動一格，指向字符串 y 的首字符。的首字符。MFA M 的瞬時移動描述：的瞬時移動描述：有窮狀態自動機定義有窮狀態自動機定義與表示與表示FA M 的瞬時移動序列描述的瞬時移動序列描述： ：M 從已識別的字符串從已識別的字符串 出發，經過出發，經過 n 次移動，次移動，識別的字符串變為識別

12、的字符串變為 ；亦即，存在；亦即，存在 n 個個 ID 構成序列：構成序列： , 1, 2, , n-1, ，使得使得 1 . n-1 。nMMMMM有窮狀態自動機定義有窮狀態自動機定義與表示與表示例：例： q0 abc a q1 bc abc q3注：所有移動都在注：所有移動都在 M 中進行時，可省去中進行時，可省去 推導符中的推導符中的 M，分別記為：，分別記為：n幾個特殊的瞬時移動序列描述：幾個特殊的瞬時移動序列描述： ：M 的的 ID 從從 出發，經過若干步（包含零步）移動，出發，經過若干步（包含零步）移動，變成變成 。 ：M 的的 ID 從從 出發，經過至少一步移動，變成出發，經過至

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

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

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

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

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

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

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

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

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

22、. 011C. 100011D. 1011ABCD011100所識別語言中同一長度的字符數所識別語言中同一長度的字符數這個自動機可接受的長度最小的字符是這個自動機可接受的長度最小的字符是2，共有兩個，共有兩個，01和和10。記作。記作 N(2)=2. 請問：請問：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：構造一構造一DFM，使它接受語言，使它接受語言 L= x000y | x, y 0, 1 * 。確定的有窮自動機確定的有窮自動機 DFADFA例例2： 構造一構造一DFM，使其接受語言，使其接受語言 L= 0n1m2k | n, m, k 1 。語言句子結構特征語言句子結構特征分析分析：0 在最前，在最前，1 在中間，在中間，2在最后，三者不可交叉出現；不可顛在最后，三者不可交叉出現；不可顛倒順序；字符倒順序；字符 0、1、2 的個數均不得少于的個數均不得少于 1。確定的有窮自動機確

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

25、qt (自鎖態自鎖態)：系系統一旦進入則無法離開的狀態。統一旦進入則無法離開的狀態。設計要點：設計要點：1、構造一個識別給定語言的、構造一個識別給定語言的 DFA 時，可先根據語言的主要特征，畫時，可先根據語言的主要特征，畫出該出該FA的主體框架圖，然后考慮相關細節問題。的主體框架圖，然后考慮相關細節問題。2、一旦、一旦 DFA 發現無法識別的語言句子，則進入陷阱狀態發現無法識別的語言句子，則進入陷阱狀態 qt；引入陷；引入陷阱狀態可方便阱狀態可方便 FA 的構造。的構造。 確定的有窮自動機確定的有窮自動機 DFADFA確定的有窮自動機確定的有窮自動機 DFADFA確定的有窮自動機確定的有窮自

26、動機 DFADFA 注注意：意：M的每個狀態給出了語言的等價類，所有狀態構成了語言的每個狀態給出了語言的等價類，所有狀態構成了語言上的一個劃分上的一個劃分 分析：什么是這里的分析：什么是這里的“有窮狀態有窮狀態”？（或者等價類）？（或者等價類）確定的有窮自動機確定的有窮自動機 DFADFA 注注意：意：M的每個狀態給出了語言的等價類，所有狀態構成了語言的每個狀態給出了語言的等價類，所有狀態構成了語言上的一個劃分上的一個劃分 分析：什么是這里的分析：什么是這里的“有窮狀態有窮狀態”？（或者等價類）？（或者等價類）這些等價類之間如何轉換？（這些等價類之間如何轉換？（ x xa意味著意味著 xa=

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

28、接受的語言；接受的語言；FA 的等價等。的等價等。2、確定型有窮自動機、確定型有窮自動機 DFA 的定義及其構造：的定義及其構造： 定義：定義：DFA 的狀態轉移函數的狀態轉移函數 唯一；唯一； 構造：首先，根據語言結構特征設計構造：首先，根據語言結構特征設計 DFA 主框架，然后，運用主框架，然后，運用其它未明示的信息補足其它未明示的信息補足主框架主框架設計；設計中可增設設計；設計中可增設“陷阱狀態陷阱狀態”。M第三章第三章 有窮狀態自動機有窮狀態自動機一、有窮狀態自動機一、有窮狀態自動機 FA FA 定義與表示定義與表示二、確定的有窮自動機二、確定的有窮自動機 DFADFA三、非確定的有窮

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

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

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