自動機與形式語言

1、自動機與形式語言報告人：姜勇剛 鄭奘巍電視是一個自動機從“關機狀態(tài)”開始，給出一個操作序列，如：“按下開關”、“按下開關”、“按下開關”從左到右執(zhí)行操作序列 得到終止狀態(tài)： “開機狀態(tài)”關機狀態(tài)開機狀態(tài)按下開關按下開關確定有限狀態(tài)自動機一個確定有限狀態(tài)自動機（DFA deterministic finite automaton）M 是由下述元素構成的五元組 (Q,q0,F)有窮狀態(tài)集合 Q ；有窮輸入字母表 ；轉移函數 : Q - Q；初始狀態(tài) q0；終結狀態(tài)集合 F，F 包含于 Q 。確定有限狀態(tài)自動機狀態(tài)集合狀態(tài)轉移規(guī)則初始狀態(tài)關機狀態(tài)開機狀態(tài)按下開關按下開關進行替換：關機狀態(tài)1，開機狀態(tài)

2、2 按下開關a確定有限狀態(tài)自動機狀態(tài)集合：1 , 2初始狀態(tài)：1狀態(tài)轉移規(guī)則：1a2 , 2a112aa任意給出一個操作序列，可以得到一個終止狀態(tài)：aaa2aaaaaa1用有限狀態(tài)自動機來描述形式語言如果把一些狀態(tài)定義為“可接受的終止狀態(tài)”，并且當一個輸入序列得到的終止狀態(tài)為“可接受的終止狀態(tài)”時，我們說這個序列被接受了。12aa規(guī)定2為可接受終止狀態(tài)輸入a*,長度為奇數時，被接受。長度為偶數時，不被接受。這說明，這個有限狀態(tài)自動機可以用來表示這樣的一種語言：僅由a構成的字符串，且長度為奇數只有當輸入字符串被自動機接受時，才說這種字符串是合法的語言。ab*12abb3aa,b3為“死胡同”，進

3、入這個狀態(tài)以后無論輸入什么，都不能進入2。B出現在開頭，或者從第二個字符開始出現“a”，則進入3成為不合法表達式。1為空字符串，符合條件。(ac+b)*312baccba,b,ca確定有限狀態(tài)自動機一個確定有限狀態(tài)自動機（DFA deterministic finite automaton）M 是由下述元素構成的五元組 (Q,q0,F)有窮狀態(tài)集合 Q ；有窮輸入字母表 ；轉移函數 : Q - Q；初始狀態(tài) q0；終結狀態(tài)集合 F，F 包含于 Q 。有限自動機是一個有向圖，這個有向圖可以用來判斷一個語句是不是合法的語言可以證明，任意正則表達式可以用一個有限狀態(tài)自動機來表示,任意有限狀態(tài)自動機都

4、可以表示一個正則表達式。這意味著，有限自動機和正則表達式是等價的所以：用有限自動機可以用來表示一種語言DFA和正則表達式的轉化a+baa*ababab等價性證明思路：遞歸構造法“形式語言”的重點是“形式”，這種形式可以被嚴格的識別而不會產生。嚴格的語言可以用自動機來表示，這意味著計算機也可以準確的理解并識別這種語言用程序實現DFA用一個有向圖來表示DFA，圖中每一個節(jié)點表示一個狀態(tài)，每一條有向邊表示一個狀態(tài)轉移規(guī)則對終止節(jié)點做特殊的標記每一個節(jié)點的出度都等于字母表中元素個數，因此用鄰接鏈表來表示圖，節(jié)點的第i條邊表示從這個節(jié)點輸入第i個字母后轉移到的節(jié)點(ac+b)*312baccba,b,ca自動機的應用字符串匹配算法（KMP）給出文本串T，模板串P，找出T中所有與P相同的子串構建模板串P的