計算引論 有限自動機

計算引論有限自動機第1頁，共24頁，2023年，2月20日，星期四第三章文法與語言3.1集合關(guān)系語言3.2有限自動機3.3上下文無關(guān)語言3.4上下文無關(guān)語言識別算法第2頁，共24頁，2023年，2月20日，星期四3.2有限自動機問題提出:如何構(gòu)造可以接受及產(chǎn)生一個語言的計算模型?語言識別器:對一個已經(jīng)存在的字符串集合,如何判斷它就是符合條件的語言?解決接受的問題語言產(chǎn)生器:怎樣根據(jù)正則表達式產(chǎn)生一個語言.解決產(chǎn)生的問題第3頁，共24頁，2023年，2月20日，星期四3.2有限自動機有限狀態(tài)圖正則表達式可以用有向圖表示，圖的結(jié)點是狀態(tài)，有一個起始結(jié)點和一個終止結(jié)點。起始結(jié)點只有出邊，終止結(jié)點用雙圓圈表示。邊上的符號表示從一個狀態(tài)到另一個狀態(tài)結(jié)點允許出現(xiàn)的字符，這種圖稱之為有限狀態(tài)圖。正則式01*

對應(yīng)的有限狀態(tài)圖為：第4頁，共24頁，2023年，2月20日，星期四3.2有限自動機例：打電話的過程，在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機，撥號，應(yīng)答，進行通話等過程，可以分別用五個狀態(tài)來表示。q0q1q2q3q4摘機收到撥號音撥號收應(yīng)答信號掛機收齊號碼q0:空閑狀態(tài)q1:等待撥號狀態(tài)q2:可以撥號狀態(tài)q3:等待應(yīng)答狀態(tài)q4:通話狀態(tài)第5頁，共24頁，2023年，2月20日，星期四3.2有限自動機有限自動機(Finiteautomaton):對實際計算機的一個嚴格限制的模型與實際計算機的共同之處是有一個固定的,計算能力有限的中央處理器.第6頁，共24頁，2023年，2月20日，星期四3.2有限自動機特點:以字符串作為輸入,通過輸入帶傳送字符串;除了提示輸入的字符串是否接受外,沒有任何其他的輸出;在它的固定中央處理器的外面完全沒有記憶功能;類似一個語言識別器.第7頁，共24頁，2023年，2月20日，星期四3.2有限自動機有限自動機的構(gòu)造abababab有限控制器q0q5q4q3q1q2輸入帶讀頭第8頁，共24頁，2023年，2月20日，星期四3.2有限自動機組成:輸入帶:放字符串的裝置有限控制器:含不同的內(nèi)部狀態(tài)讀寫頭原理:在一定的時間間隔內(nèi),自動機根據(jù)從輸入帶上讀入的符號和當前的內(nèi)部狀態(tài),進入一個新的狀態(tài).第9頁，共24頁，2023年，2月20日，星期四3.2有限自動機過程:讀取一個符號后,讀寫頭向右移動一個方格,讀取下一個符號,有限控制器的內(nèi)部狀態(tài)發(fā)生改變.最終讀寫頭到達輸入串的盡頭.自動機將根據(jù)它所處的狀態(tài)來說明它是否接受讀入的字符串,如果此時的狀態(tài)正好是一個最終狀態(tài),則認為該字符串是可接受的.第10頁，共24頁，2023年，2月20日，星期四3.2有限自動機根據(jù)每次轉(zhuǎn)換后的狀態(tài)是否唯一,可將有限自動機分為確定型有限自動機和非確定型有限自動機,本課程只介紹確定型有限自動機.第11頁，共24頁，2023年，2月20日，星期四3.2有限自動機定義:確定型有限自動機為一個五元組M=(Q,∑,,s,F),其中Q為狀態(tài)的有限集合∑為字母表sQ為起始狀態(tài)FQ為終止狀態(tài)集為Q∑Q的轉(zhuǎn)換函數(shù)第12頁，共24頁，2023年，2月20日，星期四3.2有限自動機轉(zhuǎn)換函數(shù)說明了自動機M下一步將進入的狀態(tài).若M當前狀態(tài)為qQ,從輸入帶上讀入的符號為a∑,則(q,a)Q為Q中唯一確定的狀態(tài).第13頁，共24頁，2023年，2月20日，星期四3.2有限自動機格局:機器的狀態(tài)(有限控制器,讀寫頭和輸入帶)的表示方式.連續(xù)時刻的格局序列就是自動機在輸入字符串上的計算(computation).格局是由當前狀態(tài)和字符串未輸入部分決定,即確定型有限自動機(Q,,,s,F)的格局是Q*中任意一個元素.例如上圖中的格局為(q2,ababab)第14頁，共24頁，2023年，2月20日，星期四3.2有限自動機若M的一個格局經(jīng)過一步(讀寫頭)的移動到達另一個格局,則稱這兩個格局之間有二元關(guān)系?M.例如,若(q,w)和(q’,w’)為M的格局,當且僅當對某a∈有w=aw’及(q,a)=q’時有(q,w)?M(q’,w’).此時稱(q,w)一步產(chǎn)生(q’,w’).第15頁，共24頁，2023年，2月20日，星期四3.2有限自動機?M的自反傳遞閉包表示為?*M;用(q,w)?*M(q’,w’)表示(q,w)經(jīng)過多步(包括0步)后產(chǎn)生了(q’,w’).字符串w∈*被M接受當且僅當存在狀態(tài)qF,使得(s,w)?*M(q,e).所有由被M接受的字符串組成的集合即為M接受的語言,記為L(M).第16頁，共24頁，2023年，2月20日，星期四3.2有限自動機例,令M為確定型有限自動機(Q,,,s,F),其中Q={q0,q1},={a,b},s=q0,F={q0},為如右表所示qw(q,w)q0aq0q0bq1q1aq1q1bq0第17頁，共24頁，2023年，2月20日，星期四3.2有限自動機若輸入為aabba,M的初始格局為(q0,aabba)則有(q0,aabba)?M(q0,abba)?M(q0,bba)?M(q1,ba)?M(q0,a)?M(q0,e)即(q0,aabba)?*M(q0,e),因此aabba被M接受第18頁，共24頁，2023年，2月20日，星期四a>3.2有限自動機狀態(tài)圖狀態(tài)用結(jié)點表示,用標有b的從q0指向q1的箭頭表示(q0,b)=q1,終止狀態(tài)用雙圓圈表示,起始狀態(tài)用>表示q0bbq1a第19頁，共24頁，2023年，2月20日，星期四3.2有限自動機例,設(shè)計一個確定型有限自動機M,可以接受語言:L(M)={v{a,b}*:v不含三個連續(xù)的b}第20頁，共24頁，2023年，2月20日，星期四3.2有限自動機

令M=(Q,∑,,s,F),其中Q={q0,q1,q2,q3}∑={a,b},s=q0,F={q0,q1,q2}表格表示如下:第21頁，共24頁，2023年，2月20日，星期四3.2有限自動機qw(q,w)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq3第22頁，共24頁，2023年，2月20日，星期四baq3>3.2有限自動機只要讀入a,M的狀態(tài)如果為q0,q1或q2,M都會到達q0狀態(tài)q0,q1和q2都為終止狀態(tài),