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

第三章文法與語言3.1集合關(guān)系語言3.2有限自動(dòng)機(jī)3.3上下文無關(guān)語言3.4上下文無關(guān)語言識(shí)別算法第三章文法與語言3.1集合關(guān)系語言13.2有限自動(dòng)機(jī)問題提出:如何構(gòu)造可以接受及產(chǎn)生一個(gè)語言的計(jì)算模型?語言識(shí)別器:對一個(gè)已經(jīng)存在的字符串集合,如何判斷它就是符合條件的語言?解決接受的問題語言產(chǎn)生器:怎樣根據(jù)正則表達(dá)式產(chǎn)生一個(gè)語言.解決產(chǎn)生的問題3.2有限自動(dòng)機(jī)問題提出:如何構(gòu)造可以接受及產(chǎn)生一個(gè)語23.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*

對應(yīng)的有限狀態(tài)圖為：3.2有限自動(dòng)機(jī)有限狀態(tài)圖33.2有限自動(dòng)機(jī)例：打電話的過程，在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過程，可以分別用五個(gè)狀態(tà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)3.2有限自動(dòng)機(jī)例：打電話的過程，在一次呼叫中，從建立連43.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)(Finiteautomaton):對實(shí)際計(jì)算機(jī)的一個(gè)嚴(yán)格限制的模型與實(shí)際計(jì)算機(jī)的共同之處是有一個(gè)固定的,計(jì)算能力有限的中央處理器.3.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)(Finiteautomat53.2有限自動(dòng)機(jī)特點(diǎn):以字符串作為輸入,通過輸入帶傳送字符串;除了提示輸入的字符串是否接受外,沒有任何其他的輸出;在它的固定中央處理器的外面完全沒有記憶功能;類似一個(gè)語言識(shí)別器.3.2有限自動(dòng)機(jī)特點(diǎn):63.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)的構(gòu)造abababab有限控制器q0q5q4q3q1q2輸入帶讀頭3.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)的構(gòu)造abababab有限控制73.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).3.2有限自動(dòng)機(jī)組成:83.2有限自動(dòng)機(jī)過程:讀取一個(gè)符號(hào)后,讀寫頭向右移動(dòng)一個(gè)方格,讀取下一個(gè)符號(hào),有限控制器的內(nèi)部狀態(tài)發(fā)生改變.最終讀寫頭到達(dá)輸入串的盡頭.自動(dòng)機(jī)將根據(jù)它所處的狀態(tài)來說明它是否接受讀入的字符串,如果此時(shí)的狀態(tài)正好是一個(gè)最終狀態(tài),則認(rèn)為該字符串是可接受的.3.2有限自動(dòng)機(jī)過程:93.2有限自動(dòng)機(jī)根據(jù)每次轉(zhuǎn)換后的狀態(tài)是否唯一,可將有限自動(dòng)機(jī)分為確定型有限自動(dòng)機(jī)和非確定型有限自動(dòng)機(jī),本課程只介紹確定型有限自動(dòng)機(jī).3.2有限自動(dòng)機(jī)根據(jù)每次轉(zhuǎn)換后的狀態(tài)是否唯一,可將有限103.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ù)3.2有限自動(dòng)機(jī)定義:確定型有限自動(dòng)機(jī)為一個(gè)五元組113.2有限自動(dòng)機(jī)轉(zhuǎn)換函數(shù)說明了自動(dòng)機(jī)M下一步將進(jìn)入的狀態(tài).若M當(dāng)前狀態(tài)為qQ,從輸入帶上讀入的符號(hào)為a∑,則(q,a)Q為Q中唯一確定的狀態(tài).3.2有限自動(dòng)機(jī)轉(zhuǎn)換函數(shù)說明了自動(dòng)機(jī)M下一步將進(jìn)入的狀態(tài)123.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)3.2有限自動(dòng)機(jī)格局:機(jī)器的狀態(tài)(有限控制器,讀寫頭133.2有限自動(dòng)機(jī)若M的一個(gè)格局經(jīng)過一步(讀寫頭)的移動(dòng)到達(dá)另一個(gè)格局,則稱這兩個(gè)格局之間有二元關(guān)系?M.例如,若(q,w)和(q’,w’)為M的格局,當(dāng)且僅當(dāng)對某a∈有w=aw’及(q,a)=q’時(shí)有(q,w)?M(q’,w’).此時(shí)稱(q,w)一步產(chǎn)生(q’,w’).3.2有限自動(dòng)機(jī)若M的一個(gè)格局經(jīng)過一步(讀寫頭)的移動(dòng)到143.2有限自動(dòng)機(jī)?M的自反傳遞閉包表示為?*M;用(q,w)?*M(q’,w’)表示(q,w)經(jīng)過多步(包括0步)后產(chǎn)生了(q’,w’).字符串w∈*被M接受當(dāng)且僅當(dāng)存在狀態(tài)qF,使得(s,w)?*M(q,e).所有由被M接受的字符串組成的集合即為M接受的語言,記為L(M).3.2有限自動(dòng)機(jī)?M的自反傳遞閉包表示為?*M;用(q153.2有限自動(dòng)機(jī)例,令M為確定型有限自動(dòng)機(jī)(Q,,,s,F),其中Q={q0,q1},={a,b},s=q0,F={q0},為如右表所示qw(q,w)q0aq0q0bq1q1aq1q1bq03.2有限自動(dòng)機(jī)例,令M為確定型有限自動(dòng)機(jī)(Q,,163.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接受3.2有限自動(dòng)機(jī)若輸入為aabba,M的初始格局為(q17a>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)用>表示q0bbq1aa>3.2有限自動(dòng)機(jī)狀態(tài)圖q0bbq1a183.2有限自動(dòng)機(jī)例,設(shè)計(jì)一個(gè)確定型有限自動(dòng)機(jī)M,可以接受語言:L(M)={v{a,b}*:v不含三個(gè)連續(xù)的b}3.2有限自動(dòng)機(jī)例,設(shè)計(jì)一個(gè)確定型有限自動(dòng)機(jī)M,可以193.2有限自動(dòng)機(jī)

令M=(Q,∑,,s,F),其中

Q={q0,q1,q2,q3}∑={a,b},s=q0,F={q0,q1,q2}表格表示如下:3.2有限自動(dòng)機(jī)令M=(Q,∑,,s,F203.2有限自動(dòng)機(jī)qw(q,w)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq33.2有限自動(dòng)機(jī)qw(q,w)q0aq0q0bq1q21baq3>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),所以任何不包含三個(gè)連續(xù)b的輸入字符串都可以被接受.一旦出現(xiàn)三個(gè)連續(xù)b,M會(huì)進(jìn)入q3狀態(tài),即死亡狀態(tài).aq0abbbaq1q2baq3>3.2有限自動(dòng)機(jī)只要讀入a,M的狀態(tài)如果為q223.2有限自動(dòng)機(jī)定理:語言是正規(guī)的當(dāng)且僅當(dāng)它可以被有限自動(dòng)機(jī)接受3.2有限自動(dòng)機(jī)定理:語言是正規(guī)的當(dāng)且僅當(dāng)它可以被有限23第三章文法與語言3.1集合關(guān)系語言3.2有限自動(dòng)機(jī)3.3上下文無關(guān)語言3.4上下文無關(guān)語言識(shí)別算法第三章文法與語言3.1集合關(guān)系語言243.2有限自動(dòng)機(jī)問題提出:如何構(gòu)造可以接受及產(chǎn)生一個(gè)語言的計(jì)算模型?語言識(shí)別器:對一個(gè)已經(jīng)存在的字符串集合,如何判斷它就是符合條件的語言?解決接受的問題語言產(chǎn)生器:怎樣根據(jù)正則表達(dá)式產(chǎn)生一個(gè)語言.解決產(chǎn)生的問題3.2有限自動(dòng)機(jī)問題提出:如何構(gòu)造可以接受及產(chǎn)生一個(gè)語253.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*

對應(yīng)的有限狀態(tài)圖為：3.2有限自動(dòng)機(jī)有限狀態(tài)圖263.2有限自動(dòng)機(jī)例：打電話的過程，在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過程，可以分別用五個(gè)狀態(tà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)3.2有限自動(dòng)機(jī)例：打電話的過程，在一次呼叫中，從建立連273.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)(Finiteautomaton):對實(shí)際計(jì)算機(jī)的一個(gè)嚴(yán)格限制的模型與實(shí)際計(jì)算機(jī)的共同之處是有一個(gè)固定的,計(jì)算能力有限的中央處理器.3.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)(Finiteautomat283.2有限自動(dòng)機(jī)特點(diǎn):以字符串作為輸入,通過輸入帶傳送字符串;除了提示輸入的字符串是否接受外,沒有任何其他的輸出;在它的固定中央處理器的外面完全沒有記憶功能;類似一個(gè)語言識(shí)別器.3.2有限自動(dòng)機(jī)特點(diǎn):293.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)的構(gòu)造abababab有限控制器q0q5q4q3q1q2輸入帶讀頭3.2有限自動(dòng)機(jī)有限自動(dòng)機(jī)的構(gòu)造abababab有限控制303.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).3.2有限自動(dòng)機(jī)組成:313.2有限自動(dòng)機(jī)過程:讀取一個(gè)符號(hào)后,讀寫頭向右移動(dòng)一個(gè)方格,讀取下一個(gè)符號(hào),有限控制器的內(nèi)部狀態(tài)發(fā)生改變.最終讀寫頭到達(dá)輸入串的盡頭.自動(dòng)機(jī)將根據(jù)它所處的狀態(tài)來說明它是否接受讀入的字符串,如果此時(shí)的狀態(tài)正好是一個(gè)最終狀態(tài),則認(rèn)為該字符串是可接受的.3.2有限自動(dòng)機(jī)過程:323.2有限自動(dòng)機(jī)根據(jù)每次轉(zhuǎn)換后的狀態(tài)是否唯一,可將有限自動(dòng)機(jī)分為確定型有限自動(dòng)機(jī)和非確定型有限自動(dòng)機(jī),本課程只介紹確定型有限自動(dòng)機(jī).3.2有限自動(dòng)機(jī)根據(jù)每次轉(zhuǎn)換后的狀態(tài)是否唯一,可將有限333.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ù)3.2有限自動(dòng)機(jī)定義:確定型有限自動(dòng)機(jī)為一個(gè)五元組343.2有限自動(dòng)機(jī)轉(zhuǎn)換函數(shù)說明了自動(dòng)機(jī)M下一步將進(jìn)入的狀態(tài).若M當(dāng)前狀態(tài)為qQ,從輸入帶上讀入的符號(hào)為a∑,則(q,a)Q為Q中唯一確定的狀態(tài).3.2有限自動(dòng)機(jī)轉(zhuǎn)換函數(shù)說明了自動(dòng)機(jī)M下一步將進(jìn)入的狀態(tài)353.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)3.2有限自動(dòng)機(jī)格局:機(jī)器的狀態(tài)(有限控制器,讀寫頭363.2有限自動(dòng)機(jī)若M的一個(gè)格局經(jīng)過一步(讀寫頭)的移動(dòng)到達(dá)另一個(gè)格局,則稱這兩個(gè)格局之間有二元關(guān)系?M.例如,若(q,w)和(q’,w’)為M的格局,當(dāng)且僅當(dāng)對某a∈有w=aw’及(q,a)=q’時(shí)有(q,w)?M(q’,w’).此時(shí)稱(q,w)一步產(chǎn)生(q’,w’).3.2有限自動(dòng)機(jī)若M的一個(gè)格局經(jīng)過一步(讀寫頭)的移動(dòng)到373.2有限自動(dòng)機(jī)?M的自反傳遞閉包表示為?*M;用(q,w)?*M(q’,w’)表示(q,w)經(jīng)過多步(包括0步)后產(chǎn)生了(q’,w’).字符串w∈*被M接受當(dāng)且僅當(dāng)存在狀態(tài)qF,使得(s,w)?*M(q,e).所有由被M接受的字符串組成的集合即為M接受的語言,記為L(M).3.2有限自動(dòng)機(jī)?M的自反傳遞閉包表示為?*M;用(q383.2有限自動(dòng)機(jī)例,令M為確定型有限自動(dòng)機(jī)(Q,,,s,F),其中Q={q0,q1},={a,b},s=q0,F={q0},為如右表所示qw(q,w)q0aq0q0bq1q1aq1q1bq03.2有限自動(dòng)機(jī)例,令M為確定型有限自動(dòng)機(jī)(Q,,393.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接受3.2有限自動(dòng)機(jī)若輸入為aabba,M的初始格局為(q40a>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)用>表示q0bbq1aa>3.2