[理學(xué)]編譯原理第三章(編輯修改稿)
2024-11-12 21:34 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 窮自動(dòng)機(jī)分為： 不確定自動(dòng)機(jī) NFA 確定自動(dòng)機(jī) DFA 三、不確定有窮自動(dòng)機(jī) NFA 不確定有窮自動(dòng)機(jī)的組成 ? 符號(hào)集 ?； ? 狀態(tài)集合 S={S0,S1,… .Sn}。 ? 開(kāi)始狀態(tài) S0； ? 轉(zhuǎn)換函數(shù) ?： S ?（ ???） ? S； ? 終止?fàn)顟B(tài)集： {Si1,Si2,… ..Sik}. 不確定有窮自動(dòng)機(jī)的表示方法 (1)根據(jù)定義的描述法 (2)狀態(tài)轉(zhuǎn)換圖法 (3)狀態(tài)轉(zhuǎn)換表法 不確定有窮自動(dòng)機(jī)的特點(diǎn) 從同一個(gè)狀態(tài)出發(fā)的不同邊上可以標(biāo)注相同的符號(hào)； 允許有 ?邊 。 稱字符串 a1,a2,…an 被有窮自動(dòng)機(jī)所接受，如果存在 狀態(tài)序列 S0， S1， …Sn, 使得 S0 S1, S1 S2, …, Sn 1 Sn 其中 S0為初始狀態(tài)， Sn為一個(gè)終止?fàn)顟B(tài)，中間狀態(tài)可以為初始狀態(tài)，也可為一個(gè)終止?fàn)顟B(tài)。 稱一個(gè)自動(dòng)機(jī)所能接受的所有符號(hào)串構(gòu)成的集合為該 自動(dòng)機(jī)所接受的語(yǔ)言。 例： P92 a1 a2 an 確定有窮自動(dòng)機(jī) 確定有窮自動(dòng)機(jī)是不確定有窮自動(dòng)機(jī)的一個(gè)特例，它要求滿足： 1）沒(méi)有 ?邊； 2）對(duì)于每個(gè)狀態(tài) s和每個(gè)輸入符號(hào) a，有且僅有一條標(biāo)有 a的邊 離開(kāi)，即從一個(gè)狀態(tài)出發(fā)的邊上不允許標(biāo)有相同的字符 例如：接受整數(shù)、實(shí)數(shù)和標(biāo)識(shí)符的自動(dòng)機(jī) 確定有窮自動(dòng)機(jī)的實(shí)現(xiàn) (1)采用狀態(tài)轉(zhuǎn)換表的實(shí)現(xiàn)方式 int scanner(char input[]){ in=0。S=S0。 ch=input[in++]。 while(TT[S,ch])!=undef amp。amp。 ch!=eof){ S=TT[S,ch]。 ch=input[in++]。} if (ch==eof amp。amp。 S?finalstates) return(1)。 else return(0)。 } (2)直接轉(zhuǎn)換法 int scanner(){ state=1。 getch(ch)。 while(state!=0 amp。amp。 ch!=eof){ switch(state) { case 1: switch(ch){ case a: state=1。break。 case b: state=2。break。 default: state=0。break。} break。 case 2: switch(ch) { case a: state=3。break。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1