計(jì)算引論 有限自動(dòng)機(jī)

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

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

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